八大经典排序算法入门
- 2019 年 10 月 14 日
- 筆記
排序算法入门
在我们初学算法的时候，最先接触到的就是排序算法，这些排序算法应用十分广泛，而且是很多算法的基础，可以说是每个程序员都必须得掌握的了。今天小编就来带你一举拿下经典的八大排序算法，每种算法都会有算法思想描述，动图演示，代码实现，复杂度及稳定性分析等。
01冒泡排序
1. 原理
假如我们要将一个无序数列升序排列，那么冒泡排序的思想就是将“大”的元素经过交换慢慢“浮”到数列顶端，具体步骤如下：
a. 从第一个元素开始，比较该元素与它的下一个元素的大小，如果第一个大于第二个就交换两个元素的位置，一直比较到序列末尾，我们称这个为一轮排序过程，此时我们可以将数组分成未排序部分和有序部分（当前只有一个最大值）；
b. 对数组的未排序部分执行一轮冒泡排序，最大值加入有序部分（排在数组倒数第二位）；
c. 继续对未排序数组执行上述操作，直到整个数组有序。
2. 演示
3. 代码实现
1 public static int[] bubbleSort(int[] array) { 2 if (array.length == 0) 3 return array; 4 for (int i = 0; i < array.length; i++){ 5 boolean isSwap = false; 6 for (int j = 0; j < array.length - 1 - i; j++) 7 if (array[j + 1] < array[j]) { 8 int temp = array[j + 1]; 9 array[j + 1] = array[j]; 10 array[j] = temp; 11 isSwap = true; 12 } 13 if(!isSwap) 14 break; 15 } 16 return array; 17 } 18
4. 时间复杂度
冒泡排序平均时间复杂度为O(n^2)，最好时间复杂度为O(n)，最坏时间复杂度为O(n^2)。
最好情况：如果待排序元素本来是正序的，那么一趟冒泡排序就可以完成排序工作，比较和移动元素的次数分别是 (n – 1) 和 0，因此最好情况的时间复杂度为O(n)。
最坏情况：如果待排序元素本来是逆序的，需要进行 (n – 1) 趟排序，所需比较和移动次数分别为 n * (n – 1) / 2和 3 * n * (n-1) / 2。因此最坏情况下的时间复杂度为O(n^2)。
5. 空间复杂度
冒泡排序使用了常数空间，空间复杂度为O(1)
6. 稳定性
当 array[j] == array[j+1] 的时候，我们不交换 array[i] 和 array[j]，所以冒泡排序是稳定的。
02选择排序
1. 原理
选择排序是从未排序序列中找到最小（大）元素，放到排序序列起始位置，然后从剩余未排序序列中继续找最小（大）元素，放到已排序序列的末尾，具体步骤如下：
a. 初始时，整个数组为无序数组A[0…n-1]，有序数组为空；
b. 第i趟排序（i=0,1,…,n-2），从A[i+1…n-1]中找到最小的元素，将它与第i个元素交换；
c. i=n-1时，排序结束。
2. 演示
3. 代码实现
1 public static int[] selectionSort(int[] array) { 2 if (array.length == 0) 3 return array; 4 for (int i = 0; i < array.length; i++) { 5 int minIndex = i; 6 for (int j = i; j < array.length; j++) { 7 if (array[j] < array[minIndex]) 8 minIndex = j; 9 } 10 int temp = array[minIndex]; 11 array[minIndex] = array[i]; 12 array[i] = temp; 13 } 14 return array; 15 }
4. 时间复杂度
简单选择排序平均时间复杂度为O(n^2)，最好时间复杂度为O(n^2)，最坏时间复杂度为O(n^2)。
最好情况：如果待排序元素本来是正序的，则移动元素次数为 0，但需要进行 n * (n – 1) / 2 次比较。
最坏情况：如果待排序元素中第一个元素最大，其余元素从小到大排列，则仍然需要进行 n * (n – 1) / 2 次比较，且每趟排序都需要移动 3 次元素，即移动元素的次数为3 * (n – 1)次。
需要注意的是，简单选择排序过程中需要进行的比较次数与初始状态下待排序元素的排列情况无关。
5. 空间复杂度
简单选择排序使用了常数空间，空间复杂度为O(1)
6. 稳定性
简单选择排序不稳定，比如序列 2、4、2、1，我们知道第一趟排序第 1 个元素 2 会和 1 交换，那么原序列中 2 个 2 的相对前后顺序就被破坏了，所以简单选择排序不是一个稳定的排序算法。
03插入排序
1. 原理
对未排序的序列，在已排序的序列中从后向前扫描，找到相应的位置插入，具体步骤如下：
a. 从第一个元素开始，认为该元素已经被排序；
b. 取出未排序数组的第一个元素a，在已经排序的元素序列中从后先前扫描，如果该元素大于a，将该元素移到下一个位置；
c.继续向前找直到找到一个元素小于或等于a，则将a插入该元素后面；
d. 重复步骤b,c，直到未排序序列为空。
2. 演示
3. 代码实现
1 public static int[] insertionSort(int[] array) { 2 if (array.length == 0) 3 return array; 4 int current; 5 for (int i = 1; i < array.length; i++) { 6 current = array[i]; 7 int preIndex = i - 1; 8 while (preIndex >= 0 && current < array[preIndex]) { 9 array[preIndex + 1] = array[preIndex]; 10 preIndex--; 11 } 12 array[preIndex + 1] = current; 13 } 14 return array; 15 }
4. 时间复杂度
直接插入排序平均时间复杂度为O(n^2)，最好时间复杂度为O(n)，最坏时间复杂度为O(n^2)。
最好情况：如果待排序元素本来是正序的，则移动元素次数为 0，但需要进行(n – 1)次比较。
最坏情况：如果待排序元素本来就是逆序，需要进行(n-1)趟排序，比较和移动的次数分别是n*(n-1)/2 和 n*(n-1)/2，所以最坏情况下时间复杂度为O(n^2)。
5. 空间复杂度
直接插入排序使用了常数空间，空间复杂度为O(1)
6. 稳定性
直接插入排序是稳定的。
04希尔排序
1. 原理
希尔排序是第一个突破O(n^2)的排序算法，是直接插入排序的改进算法，是一种缩小增量排序，具体步骤如下：
a. 将整个序列分割成gap个子序列（gap初始值一般取len/2），每个子序列由位置相差为gap的元素组成，每个子系列有n/gap个元素；
b. 对每一个子序列分别进行直接插入排序，然后缩减gap为原来的一般在进行插排；
c.当gap==1时，希尔排序变成直接插入排序，而此时序列已经基本有序，效率很高；
2. 演示
3. 代码实现
1 public static int[] ShellSort(int[] array) { 2 int len = array.length; 3 if(len == 0) 4 return array; 5 int current, gap = len / 2; 6 while (gap > 0) { 7 for (int i = gap; i < len; i++) { 8 current = array[i]; 9 int preIndex = i - gap; 10 while (preIndex >= 0 && array[preIndex] > current) { 11 array[preIndex + gap] = array[preIndex]; 12 preIndex -= gap; 13 } 14 array[preIndex + gap] = current; 15 } 16 gap /= 2; 17 } 18 return array; 19 }
4. 时间复杂度
希尔排序平均时间复杂度为O(nlogn)，最好时间复杂度为O(nlogn)，最坏时间复杂度为O(nlogn)。其时间复杂度与增量序列的选取有关。
5. 空间复杂度
希尔排序使用了常数空间，空间复杂度为O(1)
6. 稳定性
相同元素可能在不同的子序列中进行插入排序，稳定性会被打乱。
05归并排序
1. 原理
归并排序是采用分治法的排序算法，主要思想是将已有序的子序列合并成更长的有序序列，具体步骤如下：
a. 将长度为n的序列分成两个长度为n/2的子序列；
b. 对这两个子序列分别采用归并排序；
c.将两个排好序的子序列合并成一个排序序列；
2. 演示
3. 代码实现
1 public static int[] MergeSort(int[] array) { 2 if (array.length < 2) return array; 3 int mid = array.length / 2; 4 int[] left = Arrays.copyOfRange(array, 0, mid); 5 int[] right = Arrays.copyOfRange(array, mid, array.length); 6 return merge(MergeSort(left), MergeSort(right)); 7 } 8 public static int[] merge(int[] left, int[] right) { 9 int[] result = new int[left.length + right.length]; 10 int i = 0,j = 0,k = 0; 11 while (i < left.length && j < right.length) { 12 if (left[i] <= right[j]) { 13 result[k++] = left[i++]; 14 } else { 15 result[k++] = right[j++]; 16 } 17 } 18 while (i < left.length) { 19 result[k++] = left[i++]; 20 } 21 while (j < right.length) { 22 result[k++] = right[j++]; 23 } 24 return result; 25 }
4. 时间复杂度
归并排序平均时间复杂度为O(nlogn)，最好时间复杂度为O(nlogn)，最坏时间复杂度为O(nlogn)。
5. 空间复杂度
空间复杂度为O(n)
6. 稳定性
归并排序是稳定的。
06快速排序
1. 原理
快速排序就是给基准数找到其正确的索引位置的过程，它其实是基于分治的思想，具体步骤如下：
a. 在数组中选择一个基准点（基准点的选取可能影响效率）；
b. 分别从数组两端扫描，left指向起始位置，right指向末尾，先从后向前扫，如果发现有元素比该基准值小，就交换left和right对应元素的值，然后从前往后扫，如果发现有元素比该基准值大，就交换left和right对应元素值，如此往复，直到left>=right，然后把基准值放到left索引的位置；
c.以基准值最终索引的位置为分割点，分别递归地对前后两部分进行排序；
2. 演示
3. 代码实现
1 public static void Quicksort(int array[], int left, int right) { 2 if(left < right){ 3 int pos = partition(array, left, right); 4 Quicksort(array, left, pos - 1); 5 Quicksort(array, pos + 1, right); 6 } 7 } 8 public static int partition(int[] array,int left,int right) { 9 int key = array[left]; 10 while(left < right) { 11 while(left < right && array[left] <= key ) 12 left++; 13 array[right] = array[left]; 14 while(left <right && array[right] >= key) 15 right--; 16 array[left] = array[right]; 17 } 18 array[left] = key; 19 return left; 20 }
4. 时间复杂度
快速排序平均时间复杂度为O(nlogn)，最好时间复杂度为O(nlogn)，最坏时间复杂度为O(n^2)。
5. 空间复杂度
主要考虑递归时使用的栈空间，最好情况下partition每次恰好能均分序列，空间复杂度为O(logn),最坏情况下，退化为冒泡排序，空间复杂度为O(n)，平均为O(logn).
6. 稳定性
快速排序是不稳定的。
07堆排序
1. 原理
堆排序是基于堆这种数据结构的排序算法，将数组看作一棵完全二叉树的存储结构，利用完全二叉树中父节点和孩子结点之间的关系选取最大（小）元素，具体步骤如下：
a. 将数组构建成大顶堆，此时最大元素是堆顶元素；
b. 将堆顶元素与最后一个元素交换，然后对堆中除最后一个元素以外的元素重新调整为一个大根堆；
c.重复b，堆中只有一个元素；
2. 演示
3. 代码实现
1 public static int[] HeapSort(int[] array) { 2 len = array.length; 3 if (len == 0) return array; 4 buildMaxHeap(array); 5 while (len > 0) { 6 swap(array, 0, len - 1); 7 len--; 8 adjustHeap(array, 0); 9 } 10 return array; 11 } 12 public static void adjustHeap(int[] array, int i) { 13 int maxIndex = i; 14 if (2 * i + 1 < len && array[2 * i + 1] > array[maxIndex]) 15 maxIndex = 2 * i + 1; 16 if (2 * i + 2 < len && array[2 * i + 2] > array[maxIndex]) 17 maxIndex = 2 * i + 2; 18 if (maxIndex != i) { 19 swap(array, maxIndex, i); 20 adjustHeap(array, maxIndex); 21 } 22 } 23 public static void buildMaxHeap(int[] array) { 24 for (int i = (len - 2) / 2; i >= 0; i--) { 25 adjustHeap(array, i); 26 } 27 }
4. 时间复杂度
堆排序平均时间复杂度为O(nlogn)，最好时间复杂度为O(nlogn)，最坏时间复杂度为O(nlogn)。
5. 空间复杂度
堆排序使用常数空间O(1).
6. 稳定性
堆排序是不稳定的。
08计数排序
1. 原理
计数排序不是基于比较的排序算法，它要求输入数据必须是有确定范围的整数，主要原理是将输入数据转化为键存储在额外开辟的数组空间中，是一种线性时间复杂度的排序，具体步骤如下：
a. 找出数组中的最大和最小元素；
b. 统计数组中每个值为i的元素出现的次数，存入计数数组C的第i项；
c.对所有计数进行累加，从计数数组的第一个元素开始，每一项和前一项相加；
d. 反向填充数组，每个元素i放在新数组的C[i]位置，每放一个元素就将C[i]减去1.
2. 演示
3. 代码实现
1 public static int[] CountingSort(int[] array) { 2 if (array.length == 0) return array; 3 int bias, min = Integer.MAX_VALUE, max = Integer.MIN_VALUE; 4 for (int i = 0; i < array.length; i++) { 5 max = Math.max(max, array[i]); 6 min = Math.min(min, array[i]); 7 } 8 bias = -min; 9 int[] bucket = new int[max - min + 1]; 10 Arrays.fill(bucket, 0); 11 for (int i = 0; i < array.length; i++) { 12 bucket[array[i] + bias]++; 13 } 14 int index = 0, i = 0; 15 while (index < array.length) { 16 if (bucket[i] != 0) { 17 array[index] = i - bias; 18 bucket[i]--; 19 index++; 20 } else 21 i++; 22 } 23 return array; 24 }
4. 时间复杂度
计数排序时间复杂度为O(n+k)，n为遍历一趟数组计数过程的复杂度，k为遍历一趟桶取出元素过程的时间复杂度。
5. 空间复杂度
计数排序使用空间O(k)，k为桶数组的长度。
6. 稳定性
堆排序是稳定的。
关注我 获取更多知识
长按扫码关注
