【数据结构】七大排序

**内部排序：**数据全部放在内存中的排序

**外部排序：**如果数据量比较大，内存中放不下，不能在内外存之间进行数据的移动，需要放在硬盘上进行排序，这样的排序称为外部排序；

学习排序要熟练的掌握每一种排序的时间复杂度，稳定性，这样在场景中才可以运用自如；

💐1. 插入排序

🌼1.1 直接插入排序

遍历集合中的每一个元素，每一个元素都作为一个关键码与前面的元素作比较，如果小于前面的元素，前面的元素就向后移动，直到遇见比关键码大的元素，就插入在该元素后一个位置，这也会使得每一个数值作为关键码时，前面的元素都是已经排好序的；

直接插入排序特性：

1. 元素集合越接近有序，直接插入排序时间效率就越高(因为，如果前面都是13456已经排序好的，忽然遇见一个2，那么前面需要移动的元素就会更多)

2. 时间复杂度：

   最好的情况是O(n),数组本来就是有序的 例如 1 2 3 4 5

   最坏情况是O(n^2),数组是逆序的 例如 5 4 3 2 1

3. 空间复杂度：O(1)

4. 稳定性：稳定

   这里提到了稳定性，下面来解释一下什么是稳定性：

   稳定性：假设在一个序列中，出现了相同的数据，经过排序之后，这些相同的数据之间的相对位置保持不变，比如，r[i] = r[j], 在排序之前，r[i] 在 r[j] 之前，排序之后，r[i] 仍然在 r[j] 之前，则这样的排序称为是稳定的，反之是不稳定的；而且一个稳定的排序是可以变成不稳定的，但是一个不稳定的排序是不可以变成稳定的；

   

代码实现

//直接插入排序public void insert(int[] array) {//元素数量不能小于1if(array.length < 1) {return;}//定义i遍历每一个元素for(int i = 1; i<array.length; i++) {//定义j遍历i前面的元素int j = i-1;//定义关键码key保存i对应的值int key = array[i];for(; j>=0; j--) {//符合条件进行移动if(array[j] > key) {//如果这里变成>=就变成了不稳定的array[j+1] = array[j];}else {break;}}//最后将key插入array[j+1] = key;}}

🌼1.2 希尔排序

思想：希尔排序又称缩小增量法， 定义一个增量值，将集合中的数据按照这个增量值进行分组，每一组中元素之间的距离都是这个增量值，每一次缩小增量时都进行了预排序，最后增量值为1时，完成排序；

希尔排序特性：

1. 希尔排序是对直接插入排序的优化

2. 当gap > 1 时都是预排序，目的是为了让数组跟趋近有序，当gap == 1时，数组已经接近有序了，这样整体而言就可以达到优化效果；

3. 希尔排序的时间复杂多每办法确定，因为gap的取值方法很多，导致很难去计算，一般都会对gap进行除2来缩小增量

4. 稳定性：不稳定

   代码实现：

       //希尔排序public void shellSort(int[] array) {//定义增量int gap = array.length / 2;while(gap > 0) {for(int i = gap; i<array.length; i++) {int j = i - gap;int key = array[i];for(; j>=0; j -= gap) {if(array[j] > key) {array[j+gap] = array[j];}else{break;}}array[j+gap] = key;}gap /= 2;}}
   

💐2. 选择排序

🌼2.1 直接选择排序

思想：每一次从待排序的数据集合中取出最小的一个，然后与序列起始位置处的元素进行交换，直到全部待排序的元素排完；

代码实现：

//选择排序public void selectSort(int[] array) {if(array.length < 1){return;}for(int i = 0; i<array.length; i++) {//用来存放最小元素下标int min = array[i];//遍历待排序元素for(int j = i; j < array.length; j++) {//符合条件更新最小值if(array[j] < array[min]) {min = j;}}//交换swap(array, i, min);}}private void swap(int[] array, int i, int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}

🌼2.2 堆排序

堆排序，根据名字就可以了解到肯定是需要建堆的，而前面也已经讲过了建大(小)根堆的步骤，下面就直接利用现成的大根堆进行讲解；

如果要排升序建立大根堆，排降序建立小根堆，步骤如下：

1. 先建立一个大根堆

2. 交换第一个和n-i (i=1、2、3、4….)个节点，直到n-i=0时不用再交换

3. 进行向下调整，重新构建大根堆结构

   

   代码实现：

     public void heapSort(int[] array) {//建立大根堆buildHeap(array);//拿到最后一个节点的下标int len = array.length-1;for(int i = len; i>0; i--) {//交换第一个和最后一个节点值swap(array, 0, i);//向下调整shiftDown(array, 0, i);}}
   //堆排序//建立大根堆public void buildHeap(int[] array) {int len = array.length;for(int parent = (len-2)/2; parent >= 0; parent--) {shiftDown(array, parent, len);}}//向下调整private void shiftDown(int[] array, int parent, int len) {//求处孩子节点下标int child = (2*parent)+1;while(child < len) {//找到最大的那个孩子节点if(child + 1 < len && array[child] < array[child +1]){child++;}//比较父节点与孩子节点if(array[child] > array[parent]) {swap(array, parent, child);//保证子树的大根堆结构不会被破坏parent = child;child = (2*parent)+1;}else {break;}}}
   

   堆排序特性：

   1. 时间复杂度：O(N*logn),因为每一个元素都需要遍历到，每一次与堆顶元素交换后也都需要进行向下调整；
   2. 空间复杂度：O(1)
   3. 稳定性：不稳定

💐3. 交换排序

思想：对序列中的两个值进行比较，根据比较结果来交换这两个值，特点是：升序(降序)较大(较小)的值向尾部移动，值较小(较大)的数据向首部移动;

🌼3.1 冒泡排序

代码实现:

    //冒泡排序public void bubbleSort(int[] array) {int len = array.length;boolean flag = true;for(int i = 0; i<len; i++) {for(int j = 0; j<len-i-1; j++) {if(array[j] > array[j+1]) {swap(array, j, j+1);//代码优化，定义一个flagflag = false;}}//如果flag是true，说明遍历一趟下来，没有进行交换，则表示序列此时已经有序了，就不用再遍历剩下的元素了if(flag) {return;}}}

冒泡排序特性：

1. 时间复杂度：O(N^2)
2. 空间复杂度：O(1)
3. 稳定性：稳定

🌼3.2 快速排序

思想：从待排序的序列中任取一个元素作为基准值，然后遍历这个序列，让每个元素都与基准值比较，最后这个序列会根据基准分为两个左右子序列，左子序列中所有的值都比基准小，右子序列中所有的值都比基准大，然后再分别对两个子序列进行分割，最后序列就会变成有序

 //快速排序public void quick_sort(int[] array) {//定义左边界和右边界int left = 0;int right = array.length-1;//进行快速排序quickSort(array, left, right);}private void quickSort(int[] array, int left, int right) {//出口为左右边界相等时或右边界小于左边界if(right - left <=1) {return;}//求基准，此时序列会分为左右两个子序列//求基准的方法分为三种int div = partion(array);//分割成功后，根据div分为左右两部分[left, div] 和 [div+1, right]//递归[left, div]quickSort(array, left, div);//递归[right, div+1]quickSort(array, div+1, right);}

以上就是快速排序的模板，有点类似与二叉树的遍历，重点就是求基准的方法，下面介绍三种求基准的方法；

1. Hoare法

代码实现：

    private int hoare(int[] array, int left, int right) {//记录基准值int key = array[left];//记录基准值下标int pos = left;while(left < right){//寻找比基准值小的元素while(left < right && array[right] >= key) {right--;}//寻找比基准值大的元素while(left < right && array[left] <= key) {left++;}//交换swap(array, left, right);}//根据基准分割成两个子序列swap(array, left, pos);return left;}

3. 挖坑法

   

   代码实现：

   //挖坑法private int digHole(int[] array, int left, int right) {//存储基准值int key = array[left];while(left < right) {//寻找比基准小的元素while(left < right && array[right] >= key) {right--;}//将left坑填上array[left] = array[right];//寻找比基准值大的元素while(left < right && array[left] <= key) {left++;}//将right坑填上array[right] = array[left];}array[left] = key;return left;}
   

4. 前后指针法
   

   代码实现

       private int twoPointer(int[] array, int left, int right) {int pre = left;int cur = pre+1;while(cur < array.length){if(array[cur]<array[left] && array[++pre] != array[cur]) {swap(array, cur, pre);}cur++;}swap(array, left, pre);return pre;}
   

注意点：

如果利用快速排序的方法对十万个有序的数据进行排序，就造成了栈溢出，因为，如果本来就是升序的话，这颗二叉树就是一颗单支树，而采用快速排序时，是要进行递归的，每一次递归都是需要在栈上开辟空间的，造成了时间复杂度是 O(n^2), 空间复杂度是 O(n), 所以就会遭成栈溢出：

🌼3.2.1 快速排序优化

下面介绍对快速排序进行优化，为了防止栈溢出，就要减少递归次数, 如果要减少递归次数就要降低树的高度，步骤为：

1. 利用三数取中法找key

   private void quickSort(int[] array, int left, int right) {//出口为左右边界相等时或右边界小于左边界if(right - left <=1) {return;}//三数取中int mid = midOfThree(array, left, right);//和第一个交换swap(array, left, mid);//求基准，此时序列会分为左右两个子序列//求基准的方法分为三种int div = hoare(array, left, right);//int div = digHole(array, left, right);//int div = twoPointer(array, left, right);//分割成功后，根据div分为左右两部分[left, div] 和 [div+1, right]//递归[left, div]quickSort(array, left, div);//递归[right, div+1]quickSort(array, div+1, right);}private int midOfThree(int[] array, int left, int right) {//找中间值int mid = (right- left)/2+left;//查找第二大数字if(array[left] < array[right]) {//情况1： 5  3  9if(array[mid] < array[left]) {return left;}else if(array[mid] > array[right]) {//情况2：3  9  5return right;}else {return mid;}}else {//情况1：5  9  3if(array[mid] > array[left]) {return left;}else if(array[mid] < array[right]) {//情况2：9  3  5return right;}else {return mid;}}}

虽然利用三数取中法采用了降低树的高度，但是很可能还会造成栈溢出，但是如果在其他的编译器上可能就能跑过，一个原因是IDEA默认的栈空间比较小，解决方法是可以修改IDEA默认的栈空间大小：

另一个原因是对于三数取中后代码还可以进行优化：

上述三数取中法是防止出现单支树而导致栈溢出情况，从而通过降低树的高度进行解决，但是例如一下这种情况：

2.当递归到小区间时可以采用插入排序

当递归到小区间时，序列已经趋于有序了，而插入排序在序列趋于有序的情况下效率最高，所以在递归到小区间时，可以采用插入排序；

    if(right - left + 1 <= 15) {//采用插入排序insertOfRange(array, left, right);return;}public void insertOfRange(int[] array, int start, int end) {//定义i遍历每一个元素//对区间内的元素进行插入排序for(int i = start+1; i<= end; i++) {//定义j遍历i前面的元素int j = i-1;//定义关键码key保存i对应的值int key = array[i];for(; j>=0; j--) {//符合条件进行移动if(array[j] > key) {array[j+1] = array[j];}else {break;}}//最后将key插入array[j+1] = key;}}

🌼3.2.2 快速排序非递归

代码：

public void quickSortNor(int[] array, int left, int right) {Stack<Integer> stack = new Stack<>();//寻找一次基准int pivot = digHole(array, left, right);//判断左边区间是否只有一个元素if(pivot-1 > left){//表示左区间不止一个元素stack.push(left);stack.push(pivot-1);}if(pivot+1 < right) {//表示右区间不止一个元素stack.push(pivot+1);stack.push(right);}//弹出栈中元素while(!stack.isEmpty()) {//弹出左边界和右边界right = stack.pop();left = stack.pop();//再次找基准pivot = digHole(array, left, right);//判断左边区间是否只有一个元素if(pivot-1 > left){//表示左区间不止一个元素stack.push(left);stack.push(pivot-1);}if(pivot+1 < right) {//表示右区间不止一个元素stack.push(pivot+1);stack.push(right);}}}

快速排序特性：

1. 时间复杂度：O(n*logn)，因为快排对每一个元素都要操作，因为每一个元素都需要logn的时间复杂度，所以n个元素就是n *logn
2. 空间复杂度:O(logn)
3. 稳定性：不稳定

💐4. 归并排序

🌼4.1 基本思想

归并排序它是运用了分支算法的思想：分而治之，将一个序列分割成两份，对每一份再进行分割，一直分割到不能再分割，再进行合并；请看图解：

代码示例：

 //归并排序public void mergeSort(int[] array, int left, int right) {//递归出口if(left >= right) {return;}//求中间位置元素int mid = (right - left) / 2 + left;//递归左序列mergeSort(array, left, mid);//递归右序列mergeSort(array, mid+1, right);//合并两个序列，使序列有序merge(array, left, right, mid);}private void merge(int[] array, int left, int right, int mid){//申请一个数组用来存放合并后的元素int[] tmp = new int[right-left+1];//定义两个序列的首位置int start1 = left;int start2 = mid+1;//记录新数组中待存放元素的下标int index = 0;//合并序列中的元素while(start1 <= mid && start2 <= right){if(array[start1] < array[start2]) {tmp[index++] = array[start1++];}else {tmp[index++] = array[start2++];}}//检查哪一个序列没有遍历完while(start1 <= mid) {tmp[index++] = array[start1++];}while(start2 <= right) {tmp[index++] = array[start2++];}//将tmp的元素再移动到array中for(int i = 0; i<tmp.length; i++) {//i+left 定位到当前的序列的首位置，因为序列被分割后，每一个子序列的首位置都不一样array[i+left] = tmp[i];}}

归并排序特性：

1. 时间复杂度：O(n* logn)
2. 空间复杂度：O(n)，因为需要常见新数组
3. 稳定性：稳定

💐6. 海量数据进行排序

问题：如果有1G的内存，但是要对100G的的数据进行排序，应该怎么办？

解答：

因为100G的数据在内存中放不下，所以要利用外部排序，就像归并排序

外部排序：在磁盘等外部存储上进行的排序

1、将100G数据分为200份小文件，每个文件都是512M

2.将每一份文件都放进内存中进行排序

3、进行二路归并，合并200份文件