数据结构|Java排序算法详解_七大基于比较的排序算法排序算法|快速排序|java

七大基于比较排序算法
文章图片

几个前置知识点 1、排序
排序就是使一串记录，按照其中的某个或者某些关键字的大小，递增或者递减的排列起来的算法
平时的上下文中，如果提到排序，通常指的是排升序（非降序）
通常意义上的排序，都是指的原地排序（不申请额外空间）
2、稳定性
两个相等的数据，如果经过排序后，排序算法能保证其相对位置不发生变化，则我们称该算法是具备稳定性的排序算法。

文章图片

看是否是稳定性排序的技巧：如果在排序的过程当中，没有跳跃式的交换数据，那么就是稳定的排序

3、内部排序和外部排序
内部排序：将数据拉到内存中进行排序
外部排序：将数据放到磁盘中进行排序，因为数据量太大，导致内存不足以存放，例如归并排序
4、几个需要注意的问题
在讨论排序的时候，都需要从时间复杂度、空间复杂度、稳定性这几个维度来讨论
一、直接插入排序 1、原理
整个区间被分为有序区间和无序区间
每次选择无序区间的第一个元素，遍历有序区间，找到相应的的位置插入

文章图片

1）定义 i 号下标从1开始，依次向后遍历（因为0号下标的元素已经有序），i号位置元素存入 tmp
3）定义 j 始终在 i -1 号位置
4）每一趟拿到 i 号元素，从 j 开始往前依次进行对比
5）遇到 >= tmp 的数都要往后挪
array [ j ] >= tmp ， array [ j+1 ] = array [ j ] , j - - ;
array [ j ] < tmp ， break；
例如：
有一组待排序数组：8，6，10，4，9

文章图片

第一趟拿到 6，结果：6，8，10，4，9
第二趟拿到10，结果：6，8，10，4，9
第三趟拿到 4，结果：4，6，8，10，9
第四趟拿到9，结果：4，6，8，9，10

核心思想：

假定第一个元素是有序的，那么从第二个元素开始排序
每次和前面的元素进行比较
比较结果
1）比前面的小
2）比前面的大

2、实现

public static void insertSort(int[] array) { for (int i = 1 ; i < array.length ; i++) { int tmp = array[i]; int j; for (j = i - 1 ; j >= 0 ; j--) { if (array[j] > tmp) {//这里将 > 改为 >= 就可以实现为不稳定的排序 array[j+1] = array[j]; } else { //前面已经有序了 break; } } array[j+1] = tmp; } }

3、性能分析

文章图片

稳定性：稳定

注意 : 一个稳定的排序可以实现为不稳定的排序
但是一个不稳定的排序不能实现为一个稳定的排序

特点：数据越有序，时间效率越高

二、希尔排序 1、原理

引入：
如果现在有 10 000 个数据
在最坏的情况下采用直接插入排序
时间复杂度为：O（n^2） = 10 000 * 10 000 = 100 000 000
如果将这10 000个数据分为100组，每一组100个数据，每一组采用直接插入排序
那么每一组复杂度为 O（n^2）= 100 *100=10 000
100 组的时间复杂度为 100 * 10 000 = 1 000 000
所以分组进行直接插入排序可以提高效率

希尔排序法又称缩小增量法。希尔排序法的基本思想是：选定一个整数，把待排序文件中所有记录分组，所有距离相同的记录分在同一组内，并对每一组内的记录进行排序。然后重复上述分组和排序的工作。当距离=1时，所有记录在统一组内排好序。上述用到的整数称为增量序列，增量序列要求全为质数，

希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。

文章图片

2、实现

/** * 希尔排序 * */ //每一组的直接插入排序 public static void shell(int[] array,int gap) { for (int i = gap; i < array.length; i++) {//注意这里是 i++，不是 i+=gap int tmp = array[i]; int j; for (j = i-gap; j >= 0 ; j-=gap) {//这里 j-=gap if (array[j] > tmp) { array[j+gap] = array[j]; } else { break; } } array[j+gap] = tmp; } } public static void shellSort(int[] array) { int[] drr = {5,3,1}; for (int i = 0; i < drr.length; i++) { shell(array,drr[i]); } }

3、性能分析

文章图片

稳定性：不稳定

三、选择排序 1、原理
每一次从无序区间选出最大（或最小）的一个元素，存放在无序区间的最后（或最前），直到全部待排序的数据元素排完。

文章图片

思想：每次从待排序数组的后面，选取一个比当前（i）数字小的数据进行交换，直到（j）把当前的序列遍历完成，叫做一趟选择排序
i 从 0 开始遍历数组，j 从 i+1 开始
if （ j < i） , 交换，j++；
else j++；
j 遍历完一次数组叫做一趟选择排序

文章图片

——————————————————————————————————————————
例：一组数据：12，5，8，3，7
第一趟选择排序结果：3，12，8，5，7
第二趟选择排序结果：3，5，12，8，7
第三趟选择排序结果：3，5，7，12，8
第四趟选择排序结果：3，5，7，8，12

2、实现

/** * 选择排序 * 思想：每次从待排序数组的后面，选取一个比当前数字小的数据进行交换，知道把当前的序列遍历完成 */ 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[j] < array[i]) { int tmp = array[j]; array[j] = array[i]; array[i] = tmp; } } } }

3、性能分析

文章图片

稳定性：不稳定

四、堆排序（重要） 1、原理
关于堆的知识可以看这篇博客：优先级队列（堆）
基本原理也是选择排序，只是不使用遍历的方式查找无序区间最大的数，而是通过堆来选择无序区间的最大的数
注意：排升序要建大根堆，排降序要建小根堆

用升序来举例：

先将待排序序列建立为大根堆

将堆顶元素和最后一个元素进行交换，这时候最后一个元素就是最大的元素，他已经有序了。

再向下调整为大根堆，只需要调整0号下标元素

重复2、3步，直到排序完成

文章图片

2、实现
关于创建堆和向下调整部分都在堆的博客里有详细说明

/** * 4、堆排 * @param array */ public void heapSort(int[] array) { //1、创建大根堆 creatHeap(array); //2、堆顶元素和最后一个元素交换，然后调整 int end = array.length - 1; while (end > 0) { int tmp = array[0]; array[0] = array[end]; array[end] = tmp; adjustDown(array,0,end); end--; } } //创建大根堆 public void creatHeap (int[] array) { //i代表每颗子树根结点 for (int i = (array.length - 1 - 1) / 2; i >= 0 ; i--) { adjustDown(array,i,array.length); } } //向下调整 public void adjustDown(int[] array,int root,int len) { int parent = root; int child = 2*root + 1; while (child < len) { //1、有右孩子 -> 找到左右孩子的最大值 if (child + 1 < len && array[child] < array[child+1]) { child++; //保证child保存的是左右孩子的最大值 }if (array[child] > array[parent]) { int tmp = array[child]; array[child] = array[parent]; array[parent] = tmp; parent = child; child = 2*parent + 1; } else { break; } } }

3、性能分析

文章图片

稳定性：不稳定

五、冒泡排序 1、原理
在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序
2、实现

/** * 5、冒泡排序 * 这段代码中时间复杂度最好最坏都是O(n^2) * @param array */ public void bubbleSort(int[] array) { for (int i = 0; i < array.length - 1; i++) { for (int j = 0; j < array.length - 1 - i; j++) { if (array[j] > array[j+1]) { int tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; } } } }

优化

public void bubbleSort(int[] array) { for (int i = 0; i < array.length - 1; i++) { boolean flag = false; for (int j = 0; j < array.length - 1 - i; j++) { if (array[j] > array[j+1]) { int tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; flag = true; } } if (!flag) { break; } } }

3、性能分析

文章图片

稳定性：稳定

六、快速排序（重要）

快排为什么快呢？
因为采用了分治，每次都将可能性减了一半，可以将待排序序列均匀分割

1、原理

从待排序序列选择一个数，作为基准值（pivot）
Partition ：遍历整个待排序序列，将比基准值小的（可以包含相等的）放到基准值得左边，将比基准值大的放到基准值得右边
采用分治思想，对左右两个子区间采用相同的方法处理，直到区间的长度 == 1，代表序列已经有序，或者子区间的长度 ==0，代表没有数据

2、实现

/** * 6、快速排序 * @param array */ public void quickSort(int[] array) { quick(array,0,array.length-1); }public void quick(int[] array,int left,int right) { if (left >= right) { return; } //基准 int pivot = partition(array,left,right); //递归 quick(array,left,pivot-1); quick(array,pivot+1,right); }//一次快排返回基准 public int partition(int[] array,int left,int right) { int tmp = array[left]; while (left < right) {//1、在后面找比 tmp 小的元素 while (left < right && array[right] >= tmp) { right--; } if (left >= right) { break; } else { //找到了比 tmp 小的数字，放到left处 array[left] = array[right]; }//2、在前面找比 tmp 大的元素 while (left < right && array[left] <= tmp) { left++; } if (left >= right) { break; } else { //找到了比 tmp 大的数字，放到right处 array[right] = array[left]; } } //left 和 right相遇了 array[left] = tmp; return left; }

3、性能分析

文章图片

稳定性：不稳定

4、 partition
1、Hoare 法:

文章图片

private static int partition(int[] array, int left, int right) { int i = left; int j = right; int tmp = array[left]; while (i < j) { while (i < j && array[j] >= tmp) { j--; }while (i < j && array[i] <= tmp) { i++; } swap(array, i, j); } swap(array, i, left); return i; }

【数据结构|Java排序算法详解_七大基于比较的排序算法】2、挖坑法: （前面用到的）
基本思路和Hoare 法一致，只是不再进行交换，而是进行赋值（填坑+挖坑）

private static int partition(int[] array, int left, int right) { int i = left; int j = right; int tmp = array[left]; while (i < j) { while (i < j && array[j] >= tmp) { j--; }array[i] = array[j]; while (i < j && array[i] <= tmp) { i++; } array[j] = array[i]; } array[i] = tmp; return i; }

3、前后遍历法：

private static int partition(int[] array, int left, int right) { int d = left + 1; int tmp = array[left]; for (int i = left + 1; i <= right; i++) { if (array[i] < tmp) { swap(array, i, d); d++; } } swap(array, d - 1, left); return d - 1; }

5、基准值的选择

选择边上（左或者右）
随机选择
几数取中（例如三数取中）：array[left], array[mid], array[right] 大小是中间的为基准值

6、快排优化
1. 优化方式一：
针对的是在递归过程中，这个区间的数字规模变的很小且慢慢趋近于有序
因为在每一次排序之后，都慢慢趋近于有序，那么此时就可以使用直接插入排序，规定一个区间比如100

public void quickSort(int[] array) { quick(array,0,array.length-1); }public void quick(int[] array,int left,int right) { if (left >= right) { return; }//优化方式一 if (right - left + 1 <= 100) { insert_Sort(array,left,right); return; }int pivot = partition(array,left,right); quick(array,left,pivot-1); quick(array,pivot+1,right); } public static void insert_Sort(int[] array,int left,int right) { for (int i = left + 1 ; i <= right ; i++) { int tmp = array[i]; int j; for (j = i - 1 ; j >= left ; j--) { if (array[j] >= tmp) { array[j+1] = array[j]; } else { //前面已经有序了 break; } } array[j+1] = tmp; } }

2. 优化方式二
针对的是数据有序的情况下
随机选取基准、三数取中法

public void quickSort(int[] array) { quick(array,0,array.length-1); }public void quick(int[] array,int left,int right) { if (left >= right) { return; }//优化方式二：针对数据有序的情况下三数取中 //功能：让 left 下标的值尽可能在partition函数中，能够均匀的划分待排序序列 selectPivotMedianOfThere(array,left,right); int pivot = partition(array,left,right); quick(array,left,pivot-1); quick(array,pivot+1,right); }public static void swap(int[] array,int left,int right) { int tmp = array[left]; array[left] = array[right]; array[right] = tmp; } public void selectPivotMedianOfThere(int[] array,int left,int right) { int mid = (right + left) >>> 1; if (array[left] > array[right]) { swap(array,left,right); }if (array[left] < array[mid]) { swap(array,left,mid); }if (array[mid] > array[right]) { swap(array,mid,right); }//array[mid] <= array[left] <= array[right] }

7、非递归实现
将左右的left、right依次压入栈中

/** * 快速排序非递归 */ public void quickNor(int[] array) { Stack stack = new Stack<>(); stack.push(array.length - 1); stack.push(0); while (!stack.isEmpty()) { int left = stack.pop(); int right = stack.pop(); if (left >= right) { continue; } int pivot = partition(array, left, right); stack.push(right); stack.push(pivot + 1); stack.push(pivot - 1); stack.push(left); } }

8、优化总结

选择基准值很重要，通常使用几数取中法
partition 过程中把和基准值相等的数也选择出来
待排序区间小于一个阈值时（例如 48），使用直接插入排序

七、归并排序（重要） 1、原理
归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

文章图片

文章图片

2、实现

/** * 7、合并排序 * @param array */ public void mergeSort(int[] array) { mergeSortInternal(array,0,array.length); }public void mergeSortInternal(int[] array,int low,int high) {if (low >= high) {//分解完毕 return; }int mid = (low+high) >>> 1; mergeSortInternal(array,low,mid); mergeSortInternal(array,mid+1,high); //合并 merge(array,low,mid,high); }//合并两个有序归并段 public void merge(int[] array,int low,int mid,int high) { int s1 = low; //第一个归并段的第一个元素下标 int s2 = mid + 1; //第二个归并段的第一个元素下标 int len = high-low+1; int[] tmp = new int[len]; //每次归并段合并之后的数组 int i = 0; //临时数组tmp的下标//两个归并段都有数据 while (s1 <= mid && s2 <= high) { if (array[s1] <= array[s2]) { tmp[i++] = array[s1++]; } else { tmp[i++] = array[s2++]; } } while (s1 <= mid) {//s2没有数据，s1还有数据 tmp[i++] = array[s1++]; } while (s2 <= high) {//s1没有数据，s2还有数据 tmp[i++] = array[s2++]; }//把临时数组内的数据拷贝到原有的数组 for (int j = 0; j < len; j++) { array[low+j] = tmp[j]; } }

3、性能分析

文章图片

稳定性：稳定

4、非递归实现

文章图片

/** * 归并排序非递归 */ public void merge(int[] array,int gap) { int[] tmp = new int[array.length]; //临时数组 int k = 0; //临时数组下标 int s1 = 0; //第一个归并段起始位置 int e1 = s1 + gap -1; //第一个归并段结束位置 int s2 = e1 + 1; //第二个归并段开始位置 int e2 = s2 + gap - 1 >= array.length ? array.length-1 : s2+gap-1; //第二个归并段结束位置(可能跟第一个归并段元素个数不一样)//1、判断是否有两个归并段 && 两个归并段都有数据 while (s2 < array.length) { //开始比较 while (s1 <= e1 && s2 <= e2) { if (array[s1] <= array[s2]) { tmp[k++] = array[s1++]; } else { tmp[k++] = array[s2++]; } }while (s1 <= e1) { tmp[k++] = array[s1++]; } while (s2 <= e2) { tmp[k++] = array[s2++]; } //两个归并段完成//新的s1，e1，s2，e2 s1 = e2 + 1; e1 = s1 + gap - 1; s2 = e1 + 1; e2 = s2 + gap - 1 >= array.length ? array.length-1 : s2+gap-1; }//2、没有第二个归并段了，只有一个归并段 while (s1 <= array.length-1) { tmp[k++] = array[s1++]; }//3、所有的数据已经放入到tmp中 for (int i = 0; i < array.length; i++) { array[i] = tmp[i]; } }

5、海量数据的排序问题
外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序