七大经典排序算法 -- 比较排序（附加排序动图演示）

目录

• • • 1. 常见排序算法分类
    • 2. 排序算法的实现
    • • 2.1 直接插入排序
      • 2.2 希尔排序
      • 2.3 选择排序
      • 2.4 堆排序
      • 2.5 冒泡排序
      • 2.6 快速排序
      • • 2.6.1 递归法
        • 2.6.2 非递归法
      • 2.7 归并排序
      • • 2.7.1 递归法
        • 2.7.2 非递归法
    • 3. 排序算法时间、空间复杂度总结

1. 常见排序算法分类

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

• 内部排序：数据元素全部放在内存中的排序。 （本篇博客讲的都属于内部排序~）
• 外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。
• 稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，若两个相同的数排完序之后还能保持原有的顺序，则称之为稳定的排序，否则是不稳定的排序。

下图是总结的排序算法简单的一个思维导图，以及它们各自的算法思想！

2. 排序算法的实现

2.1 直接插入排序

算法思想：默认第一个数字是有序的，从第二个数字开始依次和前面的数字进行比较，如果发现有比该数大的数字，则将大数向后移动，直到发现比该数小的数字或者数组下标越界的时候，再将该数插入到合适位置。

 public static void insertSort(int[] array) {     for (int i = 1; i < array.length; i++) {  int temp = array[i];  int j = 0;  for (j = i-1; j >= 0; j--) {      if (array[j] > temp) {   array[j + 1] = array[j];      }else {   break;      }  }  array[j + 1] = temp;     } }

• 直接插入排序特性总结：
  ① 元素集合规模越小或者越接近有序时，直接插入排序算法的时间效率越高！！！
  ② 时间复杂度：O(n^2)，最好情况下（数组本来就是有序的情况下）是O(n)
  ③ 空间复杂度：O(1)
  ④ 稳定性：稳定，没有发生跳跃式交换

2.2 希尔排序

算法思想：又叫缩小增量排序，首先它把较大的数据集合分割成若干个小组（逻辑上分组），然后对每一个小组组内分别进行直接插入排序，此时直接插入排序所作用的数据量比较小（每一个小组），插入的效率比较高。如此说来，那么希尔排序就可以说是对直接插入排序的优化！

public static void shellSort(int[] array) {int[] drr = {5, 3, 1};//假设增量序列如此//不管是几组，算法思想都是一样的for (int i = 0; i < drr.length; i++) {shell(array, drr[i]);}}public static void shell(int[] array, int gap) {for (int i = gap; i < array.length; i++) {int temp = array[i];int j = 0;for (j = i - gap; j >= 0; j -= gap) {if (array[j] > temp) {array[j + gap] = array[j];} else {break;}}array[j+gap] = temp;}}

• 希尔排序特性总结：
  ① 希尔排序是对直接插入排序的优化
  ② 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果
  ③ 时间复杂度：O(n^1.3) ~ O(n^1.5)，（时间复杂度不好计算，需要进行推导）
  ④ 空间复杂度：O(1)
  ⑤ 稳定性：不稳定

2.3 选择排序

算法思想：i 等于待排序序列的开始，j 等于待排序序列的后一个元素，j 往后找比 i 小的数字，两者进行交换，走完一次之后就可以找到最小的元素。

public static void selectSort(int[] array) {for (int i = 0; i < array.length; i++) {for (int j = i + 1; j < array.length; j++) {if (array[i] > array[j]) {  int temp = array[i];array[i] = array[j];array[j] = array[i];}}}}

• 选择排序特性总结：
  ① 直接选择排序思考非常好理解，但是效率不是很好，实际中很少使用
  ② 时间复杂度：O(n^2)
  ③ 空间复杂度：O(1)
  ④ 稳定性：不稳定

2.4 堆排序

堆排序请移步这里哦~

2.5 冒泡排序

算法思想：它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来，越大的元素会经由交换慢慢“浮”到数列的顶端。

• 根据以上规律，可得假设待排序序列中有n个元素，趟数用i表示，那么一共会进行n-1趟排序，每趟比较n-i次。（注意，下述代码趟数是从 0 开始计算的，所以每趟会比较 n-i-1 次！）

public static void bubbleSort(int[] array) {for (int i = 0; i < array.length - 1; i++) {//控制趟数for (int j = 0; j < array.length - i - 1; j++) {//每趟比的次数if (array[j] > array[j + 1]) {int temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;}}}}

• 冒泡排序特性总结：
  ① 时间复杂度：O(n^2)
  ② 空间复杂度：O(1)
  ③ 稳定性：稳定
• 冒泡排序的优化：
  如果排了几趟之后，发现已经是有序的了，那么后面就不再需要比较了，就像上述例子一样后面三趟都是不需要的，这样一来，时间复杂度最好情况下就是O(n)了。
• 解决方法：可以考虑加个变量，一旦发现序列已经有序了，就不再进行比较了。

public static void bubbleSort(int[] array) {boolean swap = false;for (int i = 0; i < array.length - 1; i++) {//控制趟数swap = false; //因为不知道从哪一趟是不需要交换的，先置为falsefor (int j = 0; j < array.length - i - 1; j++) {//每趟比的次数if (array[j] > array[j + 1]) {int temp = array[j];array[j] = array[j + 1];array[j + 1] = temp;swap = true; //如果发现交换把swap置为true}}if (!swap) {break; //如果一趟走完没有发生交换，则已经有序了}}}

2.6 快速排序

算法思想：使用分治的思想，通过一趟排序将待排序序列分割成两部分，其中一部分记录的关键字均比另一部分记录的关键字小，之后的分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

2.6.1 递归法

public static int partion(int[] array, int low, int high) {int temp = array[low];while (low < high) {while (low < high && array[high] > temp) {high--;//high有可能会越界}array[low] = array[high];while (low < high && array[low] < temp) {low++;}array[high] = array[low];}array[low] = temp;return low;}public static void quick(int[] array, int start, int end) {//递归了多少次，par就保存了多少次int par = partion(array, start, end);//一趟快排完毕//递归左边，首先得保证左边有两个数据元素以上if (par > start + 1) {quick(array, start, par-1);}//递归右边if (par < end - 1) {quick(array, par + 1, end);}}public static void quickSort1(int[] array) {quick(array, 0, array.length - 1);}

• 快速排序的优化：
• 根据以上分析不难发现，在待排序序列可以被分割成均匀的两部分时快排效率最高，但是这显然不太符合实际，万一本来就是有序的呢？那岂不是浪费太多时间了吗？
  那么问题就在于如何把待排序序列均匀的分割成两部分？
  ① 优化1：三数取中法 array[mid] <= array[low] <= array[high]
  ② 优化2：在排序过程中，待排序序列会逐渐趋于有序。如果某一段序列已经有序，再对这一部分序列进行快排，就会变成冒泡排序。所以到达某一个区间后用直接插入排序。

public static int partion(int[] array, int low, int high) {int temp = array[low];while (low < high) {while (low < high && array[high] > temp) {high--;//high有可能会越界}array[low] = array[high];while (low < high && array[low] < temp) {low++;}array[high] = array[low];}array[low] = temp;return low;}public static void insertSort(int[] array, int start, int end) {for (int i = start + 1; i <= end; i++) {int temp = array[i];int j = 0;for (j = i-1; j >= start; j--) {if (array[j] > temp) {array[j + 1] = array[j];}else {break;}}array[j + 1] = temp;}}public static void quick(int[] array, int start, int end) {//假设对start到end这部分序列有16个元素，已经有序则进行直接插入排序if (end - start + 1 <= 16) {insertSort(array, start, end);return;//如果这部分序列用直接插入排序完成了，那么剩下的函数不需要再进行了}//每次找基准之前先三数取中一下medianOfThree(array, start, end);//递归了多少次，par就保存了多少次int par = partion(array, start, end);//一趟快排完毕//递归左边，首先得保证左边有两个数据元素以上if (par > start + 1) {quick(array, start, par - 1);}//递归右边if (par < end - 1) {quick(array, par + 1, end);}}public static void quickSort1(int[] array) {quick(array, 0, array.length - 1);}//三数取中法法找基准public static void medianOfThree(int[] array, int low, int high) {int mid = (low + high) / 2;if (array[mid] > array[low]) {swap(array, low, mid);}if (array[low] > array[high]) {swap(array, low, high);}}public static void swap(int[] array, int low, int high) {int temp = array[low];array[low] = array[high];array[high] = temp;}

• 快速排序特性总结：
  ① 时间复杂度：最好：O(n*logn) 最坏：O(n^2)
  ② 空间复杂度：最好：O(logn) 最坏：O(n) -> 123456789
  ③ 稳定性：不稳定

2.6.2 非递归法

public static int partion(int[] array, int low, int high) {int temp = array[low];while (low < high) {while (low < high && array[high] > temp) {high--;//high有可能会越界}array[low] = array[high];while (low < high && array[low] < temp) {low++;}array[high] = array[low];}array[low] = temp;return low;}public static void quickSort2(int[] array) {int low = 0;int high = array.length-1;Stack<Integer> stack = new Stack<>();int par = partion(array, low, high);if (par > low + 1) {stack.push(low);stack.push(par - 1);}if (par < high - 1) {stack.push(par + 1);stack.push(high);}while (!stack.isEmpty()) {high = stack.pop();low = stack.pop();par = partion(array, low, high);if (par > low+1) {stack.push(low);stack.push(par-1);}if (par < high-1) {stack.push(par+1);stack.push(high);}}}

2.7 归并排序

算法思想：建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

2.7.1 递归法

public static void merge1(int[] array, int start, int mid, int end, int[] tempArray) {//不断的创建销毁对象，效率太低，所以直接将tempArray作为参数传进来//int[] tempArray = new int[array.length];int tempIndex = start;//设置为start，防止把原来数据覆盖掉int i = start;//把start保存下来是为了接下来拷贝int s2 = mid + 1;//当有两个归并段并且两个归并段都有数据的时候while (start <= mid && s2 <= end) {if (array[start] < array[s2]) {tempArray[tempIndex++] = array[start++];}else {tempArray[tempIndex++] = array[s2++];}}//第一个归并段有数据，说明第二个归并段已经走完while (start <= end) {tempArray[tempIndex++] = array[start++];}//第二个归并段有数据，说明第一个归并段已经走完while (s2 <= end) {tempArray[tempIndex++] = array[s2++];}//把排好序的数据全部从tempArray拷贝到Array中while (i <= end) {array[i] = tempArray[i++];}}public static void mergeSort1(int[] array, int start, int end, int[] tempArray) {if (start >= end) {return;}int mid = (start+end)/2;//递归左边mergeSort1(array, start, mid, tempArray);//递归右边mergeSort1(array, mid+1, end, tempArray);//单个有序之后进行二路合并merge1(array, start, mid, end, tempArray);}

• 归并排序特性总结：
  ① 时间复杂度：O(n*logn)
  ② 空间复杂度：O(n)
  ③ 稳定性：稳定

2.7.2 非递归法

public static void merge2(int[] array, int gap) {//gap是每组里面的数据个数int[] tempArray = new int[array.length];int i = 0;//表示的是tempArray的下标int start1 = 0;int end1 = start1 + gap - 1;int start2 = end1 + 1;int end2 = start2 + gap - 1 <= array.length - 1 ? start2 + gap - 1 : array.length - 1; //end2可能会数组越界//保证有两个归并段//比较的时候肯定有一个归并段先没有数据while (start2 < array.length) {//两个归并段都有数据while (start1 <= end1 && start2 <= end2) {if (array[start1] < array[start2]) {tempArray[i++] = array[start1++];}else {tempArray[i++] = array[start2++];}}//第一个归并段有数据while (start1 <= end1) {tempArray[i++] = array[start1++];}//第二个归并段有数据while (start2 <= end2) {tempArray[i++] = array[start2++];}//证明一次二路归并已经完成start1 = end2 + 1;end1 = start1 + gap - 1;start2 = end1 + 1;end2 = start2+gap-1 <= array.length-1 ? start2+gap-1 : array.length-1;}//只有一个归并段while (start1 < array.length) {tempArray[i++] = array[start1++];}//把数据从tempArray拷贝到原始数组for (int j = 0; j < tempArray.length; j++) {array[i] = tempArray[j];}}public static void mergeSort2(int[] array) {//每个归并段里的数据的个数是以2倍形式增长//最少是1组，最多是array.length组for (int i = 1; i < array.length; i *= 2) {merge2(array, i);}}

3. 排序算法时间、空间复杂度总结

• 下图是各个排序算法的时间复杂度、空间复杂度及稳定性分析：