十大排序算法

1.冒泡排序

​ 利用相邻两个元素的比较，将较大的元素放在后面，这样经过一轮比较排在最后的元素就是最大的元素。依次比较n-1次，就可以得到一个升序的数组。

冒泡排序的实现：（三种方式）

方式一：

// 传入一个需要排序的数组 public void sort(int[] array){ // 每一个元素都与其前面一个元素进行比较，如果前一个元素比后一个元素大， // 则交换位置，经过一轮循环后，数组最后一个元素就是最大的元素。 // 故此处有end--，即表示无需每次遍历整个数组 for(int end = array.length - 1; end > 0; end--){ // 从索引为1的元素开始，与前一个元素进行比较 for(int begin = 1; begin <= end; begin++){ // 如果前一个元素比其大，则交换 if(array[begin] < array[begin - 1]){ int temp = array[begin]; array[begin] = array[begin - 1]; array[begin - 1] = temp; } } } }

优化方式一： （使用一个标记符，判断数组中的元素是否已经有序）

public void sort(int[] array){ for(int end = array.length - 1; end > 0; end--){ boolean sorted = true; // 用于判断此后的数组是否有序 for(int begin = 1; begin <= end; begin++){ // 如果进入该交换语句中，表示数组还是无序 if(array[begin] < array[begin - 1]){ int temp = array[begin]; array[begin] = array[begin - 1]; array[begin - 1] = temp; sorted = false; } } if(sorted){// 如果一轮循环后，没有一次进入交换语句中，表示该数组已经有序，无需继续排序 break; } } }

优化方式二： （利用一个变量，用来记录数组最后一次交换顺序的索引）

public void sort(int[] array){ for(int end = array.length - 1; end > 0; end--){ int sortIndex = 0;// 用于记录，数组最后一次执行交换顺序的位置 for(int begin = 1; begin <= end; begin++){ // 如果进入该交换语句中，表示数组还是无序 if(array[begin] < array[begin - 1]){ int temp = array[begin]; array[begin] = array[begin - 1]; array[begin - 1] = temp; sortIndex = begin;// 进入交换语句，则更新sortIndex } } end = sortIndex;// 提前终止for循环 } }

复杂度分析：

最坏、平均时间复杂度：$O(n^2)$;最好时间复杂度：$O(n)$；

空间复杂度：$O(1)$;

属于稳定排序。

2.选择排序

​ 遍历一遍数组，找到最大值，与数组末尾元素交换位置。

选择排序的实现：

public void sort(int[] array){ for(int end = array.length - 1; end > 0; end--){ int max = 0; for(int begin = 1; begin <= end; begin++){ if(array[max] < array[begin]){ max = begin;// 更新最大值的索引 } } // 将最大值与最后一个元素交换位置 int temp = array[max]; array[max] = array[end]; array[end] = temp; } }

复杂度分析：

最坏、平均、最好时间复杂度：$O(n^2)$;

空间复杂度：$O(1)$;

注：1.与冒泡排序相比，大大减小了交换的次数，平均性能优于冒泡排序。

​ 2.可通过堆来选择最大值，实现对选择排序的优化。

​ 3.属于不稳定排序。

3.堆排序

​ 采用数据结构堆来进行排序。

1.将数组元素建堆，最大堆（升序）。

2.然后交换堆顶元素与尾元素，对此时的堆顶元素进行一次下滤操作，最后将堆大小减一。

3.循环操作，直到堆中只有一个元素。此时表示原数组以及排好序。

堆排序的实现

// 假设array数组为一个全局变量，可以在某个类中定义，然后通过构造器传入一个真正的数组 public void sort(){ int heapSize = array.length;// 定义堆的大小 // 建堆 for(int i = (heapSize >> 1) - 1); i >= 0; i--){ siftDown(heapSize, i); } while(heapSize > 0){ // 1.交换堆顶元素与尾元素的位置，此时尾元素即为最大值； int temp = array[0]; array[0] = array[heapSize - 1]; array[heapSize - 1] = temp; heapSize--;// 2.然后将堆大小减一； siftDown(0);// 3.对此时的堆顶元素进行下滤操作； } } // 对堆中索引为index的元素进行下滤操作 public void siftDown(int heapSize, int index){ int element = array[index]; int half = (heapSize >> 1); while(index < half){// 当index > half时才有子节点，才需要进行下滤操作 int childIndex = (index << 1) + 1;// 默认为左子节点 int child = array[childIndex];// 左子节点的值 int rightIndex = childIndex + 1;// 右子节点 // 找到子节点中，值更大的那个节点 if(rightIndex < heapSize && array[rightIndex] > child){ child = array[childIndex = rightIndex]; } if(element >= child){// 与子节点比较，如果大于子节点，不用下滤操作，直接退出 return; } array[index] = child;// 将子节点与该元素交换位置 index = childIndex;// 更新该元素的索引 } array[index] = element;// 当找到该元素合适的位置时，才进行赋值 }

复杂度分析：

最好、最坏、平均复杂度：$O(nlogn)$;

空间复杂度：$O(1)$;

属于不稳定排序。

4.插入排序

​ 数组的左边存放已经有序的元素。将数组右边的元素依次与左边的元素进行比较，插入到合适的位置。

插入排序的实现：(3种方式)

方式一：

public void sort(int[] array){ for(int begin = 1; begin < array.length; begin++){ int cur = begin;// 表示当前要插入的元素的索引 while(cur > 0 && array[cur] < array[cur - 1]){ int temp = array[cur]; array[cur] = array[cur - 1]; array[cur - 1] = temp; cur--; } } }

优化一： （先保存要插入的元素，找到该元素的位置后再进行赋值操作）——用“挪动”来替换“交换”

public void sort(int[] array){ for(int begin = 1; begin < array.length; begin++){ int cur = begin;// 表示当前要插入的元素的索引 int element = array[cur]; while(cur > 0 && element < array[cur - 1]){ array[cur] = array[cur - 1]; cur--; } array[cur] = element;// 最后进行赋值 } }

利用二分搜索进行优化：

// 假设array数组为一个全局变量，可以在某个类中定义，然后通过构造器传入一个真正的数组 public void sort(){ for(int i = 1; i < array.length; i++){ insert(i, search(i)); } } // 将指定索引的元素插入到数组的指定位置中 public void insert(int source, int dest){ int element = array[source]; for(int i = source; i > dest; i--){ array[i] = array[i - 1]; } array[dest] = element; } // 使用二分搜索，查找指定元素在有序数组中的位置 public int search(int index){ int begin = 0;// 查找范围的起始位置为0 int end = index;// 查找范围的终止位置为index while(begin < end){// 当begin和end相同时，表示已经遍历完所有的元素 int mid = (end - begin) >> 1;// 中点 if(array[index] < array[mid]){ end = mid; } else { begin = mid + 1; } } return begin;// 返回查找到的位置 }

复杂度分析：

最坏、平均时间复杂度：$O(n^2)$；

采用二分搜索的方式进行优化只是减少了比较的次数

最好时间复杂度：$O(n)$;

空间复杂度：$O(1)$；

属于稳定排序

5.归并排序

​ 采用分治策略——先将规模较大的模块分成相同的两部分，分别对两部分进行处理，最后合并。

其中，如果分的两部分的规模还是很大，继续进行进行划分。

循环一下步骤：

1.将数组进行二分处理；

直到数组中不可再分（只有一个元素）。

2.对数组的两部分分别进行排序处理；

3.合并数组。

归并排序的实现：

// 假设array数组为一个全局变量，可以在某个类中定义，然后通过构造器传入一个真正的数组 int[] leftArray = new int[array.length >> 1];// 用来存储临时数组，因为最后的合并操作，要将左右子数组再合并到原数组中，而只通过一个数组无法做到。 public void sort(){// 为了与其他方式对应 sort(0, array.length);// 左闭右开，即[0,array.length) } // 用于递归操作，进行排序 public void sort(int begin, int end){ if(end - begin < 2){// 至少要有两个元素，否则直接退出 return; } int mid = (begin + end) >> 1;// 分别对两部分进行排序——“分” sort(begin, mid); sort(mid, end); merge(begin, mid, end);// 合并操作 } // 合并 public void merge(int begin, int mid, int end){ int li = begin; int le = mid - begin;// leftArray的当前索引与长度 int ri = mid; int re = end;// 右子数组的当前索引与长度 int ai = begin;// 原数组的索引 // 先给左数组赋值 for(int i = 0; i < le; i++){ leftArray[i] = array[i + begin]; } // 通过循环来实现合并，比较左右子数组中的元素，小的先存入原数组中 while(li < le){// 因为左右子数组长度几乎相同，如果原数组长度为奇数，此时右子数组的长度大于左子数组 if(ri < re && leftArray[li] < array[ri]){ array[ai++] = leftArray[li++]; } else { array[ai++] = array[ri++]; } } }

复杂度分析

最坏、最好、平均时间复杂度：$O(nlogn)$;

空间复杂度：$O(n)$;

属于稳定排序。

6.快速排序

​ 先找到一个轴点（pivot），然后让轴点两边的元素满足：

1.左边的元素都是小于轴点元素；

2.右边的元素都是大于轴点元素；

3.与轴点元素相等的元素随便放哪边。

4.为了让轴点元素合理，使用随机数来生成轴点元素。

快速排序的实现

// 假设array数组为一个全局变量，可以在某个类中定义，然后通过构造器传入一个真正的数组 public void sort(){ sort(0, array.length); } public void sort(int begin, int end){ if(end - begin < 2){ return; } int mid = pivotIndex(begin, end);// 以轴点来充当中点，再分别对两边进行排序 sort(begin, mid); sort(mid + 1, begin); } // 使用随机生成的轴点对数组进行一次排序，并返回轴点元素的索引 public int pivotIndex(int begin, int end){ swap(array[begin], array[(int)(Math.random() * (end - begin))]);//让起始元素与后面任意一个元素进行交换 int pivot = array[begin];// 然后让当前起始元素作为轴点 end--;// 让end指针指向最后一个元素 while(begin < end){ while(begin < end){ if(pivot < array[end]){// 当轴点元素小于其后面的元素，则end指针前移 end--; } else {// 否则将最后的元素赋值给begin指针所指向的索引，且begin指针后移 array[begin++] = array[end]; break;// 并退出循环，进行从前开始比较 } } while(begin < end){// 当轴点元素大于其后面的元素，则begin指针后移 if(pivot > array[begin]){ begin++; } else { array[end--] = array[begin]; break; } } } array[begin] = pivot;// 将轴点元素的值赋给相应的位置 return begin; }

复杂度分析：

最坏时间复杂度：$O(n^2)$;

最好、平均时间复杂度：$O(nlogn)$;

空间复杂度：$O(logn)$;

属于稳定排序。

7.希尔排序

将数组看成一个矩阵，利用步长序列来确定将数组分成几列来处理。对每一列进行排序，当步长序列最终为一列时，该数组已经排好序。

步长序列：是一组数值（降序排列），代表的是当前操作需要将数组分为几列来进行排序，最终步长值为1时，此时只有一列已经拍好序。

步长序列：有很多种，但是本文只提及两种——由希尔本人设计的shellStepSequence和目前性能最好的sedgewickStepSequence。

1.希尔本人设计的步长序列：

$$step=n/2^k其中k为1,2,3...（直到step为1）$$

2.目前性能最好的步长序列：

$$step=\{\begin{array}{l}9\ast (2^k-2^{\frac{k}{2}})+1，k=even\\ 8\ast 2^k-6\ast 2^{\frac{k+1}{2}}+1，k=odd\end{array}$$

希尔排序的实现：

// 假设array数组为一个全局变量，可以在某个类中定义，然后通过构造器传入一个真正的数组 public void sort(){ // 首先获取步长序列：可选的有希尔自己设计的步长序列（shellStepSequence）以及目前最好的sedgewickStepSequence。 List<Integer> sequence = sedgewickStepSequence(array.length); for(Integer step : sequence){ sort(step); } } // 将元素分成几列，再进行列排序 public void sort(int step){ for(int col = 0; col < step; col++){ for(int begin = col + step; begin < array.length; begin += step){ int cur = begin; // 找到最小的元素，并将其放在适合的位置 while(cur > col && array[cur] < array[cur - step]){// 与上一列的同位置元素比较，如果小于前一个元素，交换 int temp = array[cur]; array[cur] = array[cur - step]; array[cur - step] = temp; cur -= step; } } } }

步长序列：

// 步长序列生成函数——传入数组的长度 public List<Integer> sedgewickStepSequence(int length){ List<Integer> list = new ArrayList<>(); int k = 0, step = 0; while(true){ int pow1 = (int)Math.pow(2, k >> 1); if((k & 1) == 1){// 偶数 step = 9 * pow1 * (pow1 - 1) + 1; } else { int pow2 = (int)Math.pow(2, (k + 1) >> 1); step = 8 * pow1 * pow1 - 6 * pow2 + 1; } if(step >= length){ break; } list.add(0, step); k++; } return list; } public List<Integer> shellStepSequence(int length){ List<Integer> list = new ArrayList<>(); while((length >>= 1) > 0){ list.add(length); } return list; }

复杂度分析：

最好时间复杂度：$O(n)$

希尔给出的步长序列的最坏时间复杂度：$O(n^2)$

Robert Sedgewick给出的步长序列的最坏时间复杂度：$O(n^{\frac{4}{3}})$

属于稳定排序。

8.计数排序

​ 计算每个元素在数组中的出现个数，然后推断出其在数组中的索引。

计数排序的实现：

public void sort(int[] array){ int[] output = new int[array.length];// 用来存放已排好序的数组 // 找到最大值和最小值，以便之后限定计数数组的大小 int min = array[0]; int max = array[0]; for(int i = 1; i < array.length; i++){ if(max < array[i]){ max = array[i]; } if(min > array[i]){ min = array[i]; } } int[] counts = new int[max - min + 1];// 定义计数大小 for(int i = 0; i < array.length; i++){// 记录每个元素的数量 counts[array[i] - min]++; } // counts[] 数组中存放每个元素与其前面元素的个数之和 for(int i = 1; i < array.length; i++){ counts[i] += count[i - 1]; } // 根据counts中的信息，将原数组中的元素赋给output数组，此时已经是排好序的数组了 for(int i = array.length - 1; i > 0; i--){ output[--counts[array[i] - min]] = array[i]; } // 重新赋值给原数组————如果只是想得到排好序的数组，这一步可以省略。只需要将output数组返回或者打印等 for(int i = 0; i < array.length; i++){ array[i] = output[i]; } // 此处可对数组进行操作。如：返回或者直接在此处打印。 // 如果要对数组进行返回操作，则要将返回值类型变成int[] }

复杂度分析：

最好、最坏、平均时间复杂度：$O(n+k)$

空间复杂度：$O(n+k)$

属于稳定排序

9.桶排序

将所有元素都放进一个桶数组中，根据一定的规则将元素**均匀**添加到桶数组中，最后取出元素。

1.生成一定数量的桶（可用链表或者动态数组）；

2.按照一定的规则，将元素均匀分配到桶数组中；

3.分别对每个桶进行排序；

4.合并非空的桶为有序数组。

桶排序的实现：

public void sort(int[] array){ List<Double>[] buckets = new LinkedList[array.length]; // 以下操作为将元素添加到桶数组中 for(int i = 0; i < array.length; i++){ int bucketIndex = (int)(array[i] * array.length);// 生成每个元素在桶数组中的索引——规则为元素值*数组长度 List<Double> bucket = buckets[bucketIndex];// 找到桶数组中相应位置的元素 if(bucket == null){// 如果桶数组中该位置为null，表示为第一次添加，新建一个节点并将其添加到桶数组中 bucket = new LinkedList<Double>(); buckets[bucketIndex] = bucket; } bucket.add(array[i]);// 将元素添加到桶数组中 } // 对每个桶中的元素进行排序并将其添加会原数组中 int index = 0;// 用于遍历原数组中的所有位置 for(int i = 0; i < buckets.length; i++){ if(buckets[i] == null) continue; buckets[i].sort(null);// 对非空桶进行排序 for(Double e : buckets[i]){ array[index++] = e;// 将元素依次添加回原数组 } } // 此处可对数组进行操作。如：返回或者直接在此处打印。 // 如果要对数组进行返回操作，则要将返回值类型变成Double[] }

复杂度分析：

时间复杂度：$O(n)+m\ast O(\frac{n}{m}log\frac{n}{m})=O(n+nlog\frac{n}{m})=O(n+nlogn-nlogm)=O(n+k)其中k=nlogn-nlogm$;

空间复杂度：$O(n+m)m为桶的数量$;

属于稳定排序。

10.基数排序

​ 依次对个位、十位、百位……进行排序（从低位到高位）

由于每一位只能取0~9共十位，故可用计数排序进行排序操作。

基数排序的实现：（两种方式）

方式一：

// 假设array数组为一个全局变量，可以在某个类中定义，然后通过构造器传入一个真正的数组 public void sort(){ // 先找到最大值，以找到该基数排序的最大范围 int max = array[0]; for(int i = 1; i < array.length; i++){ if(max < array[i]){ max = array[i]; } } int[] output = new int[array.length];// 用来存储排好序的数组 int[] counts = new int[10];// 每一位只有十种取值 for(int divider = 1; divider <= max; divider *= 10){ // 对每一位进行排序 countSort(divider, output, counts); } // 此处可对数组进行操作。如：返回或者直接在此处打印。 // 如果要对数组进行返回操作，则要将返回值类型变成int[] } // 计数排序 public void countSort(int divider, int[] output, int[] counts){ for(int i = 0; i < array.length; i++){ counts[i] = 0; } // 得到该位（个位、十位……）上每一个数（0~9）的数量 for(int i = 0; i < array.length; i++){ counts[array[i] / divider % 10]++; } for(int i = 1; i< array.length; i++){ counts[i] += counts[i - 1]; } for(int i = array.length - 1; i >= 0; i--){ output[--counts[array[i] / divider % 10]] = array[i]; } for(int i = 0; i < array.length; i++){ array[i] = output[i]; } }

方式二： 利用桶的概念！

public void sort(int[] array){ int max = array[0]; for(int i = 1; i < array.length; i++){ if(max < array[i]){ max = array[i]; } } int[][] buckets = new int[10][array.length];// 桶数组 int[] bucketSize = new int[buckets.length];// 保存每个桶中元素的数量 for(int divider = 1; divider <= max; divider *= 10){ for(int i = 0; i < array.length; i++){ int no = array[i] / divider % 10;// 得到每个元素的位（个位、十位……）值 buckets[no][bucketSize[no]++] = array[i];// 根据位值，将元素添加到桶数组的相应位置 } int index = 0; for(int i = 0; i < buckets.length; i++){// 根据每个元素的位值，依次添加桶数组中的元素到原数组中 for(int j = 0; j < bucketSize[i]; j++){// 每个位值的元素个数。 array[index++] = buckets[i][j]; } bucketSize[i] = 0; } } // 此处可对数组进行操作。如：返回或者直接在此处打印。 // 如果要对数组进行返回操作，则要将返回值类型变成int[] }

复杂度分析：

方式一：

最好、最坏、平均时间复杂度：$O(d\ast (n+k))d为最大值的位数，k为进制数$

空间复杂度：$O(n+k)k为进制数$

属于稳定排序。

方式二：

最好、最坏、平均时间复杂度：$O(dn)$

空间复杂度：$O(kn+n)k为进制数，d为最大值的位数$

属于稳定排序。