文章目录

• 排序
• • 排序的概念及应用
  • 一、直接插入排序
  • • 1. 简介
    • 2.动图展示
    • 3.过程
    • 4.代码
    • 5.总结
  • 二、希尔排序
  • • 1.简介
    • 2.过程
    • 3.代码
    • 4.总结
  • 三、选择排序
  • • 1.简介
    • 2.代码
    • 3.总结
  • 四、堆排序
  • • 1.代码
    • 2.总结
  • 五、冒泡排序
  • • 1.过程
    • 2.代码
    • 3.总结
  • 六、快速排序
  • • 1.简介
    • 2.过程
    • 3.两种优化快速排序的思想
    • 4.代码-递归、非递归、优化
    • 5.总结
  • 七、归并排序
  • • 1.简介
    • 2.过程
    • 3.代码
    • • 1.递归
      • 2.非递归
  • 海量数据排序问题
  • • 概念
    • 过程

排序

排序的概念及应用

排序∶所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的;否则称为不稳定的。

一、直接插入排序

1. 简介

是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。

2.动图展示

3.过程

1. 将序列中第一个元素看为有序的，将数组划分为有序和无序部分

• 下标i为待排序元素下标，从1开始。n个数需要n-1次遍历。
• j=i-1
  

2.每一次插入的比较都是从前一个数开始。即i下标位置待排序元素，与有序部分[0,j]下边处的末尾元素依次向前进行比较

• 若array[i]>array[j]:则array[j+1]=array[i]
  
  下标 i 处的元素插入到 j+1 位置。
  

• 若array[i]

• array[j+1]=array[j] , 执行 j-- 操作
  

• 不断与 j 下标元素比较，出现小于2的数，找到了插入位置，所以跳出循环，2就可以插入数组了，下标是j+1
  
  3.i++，待排序元素更新，同样执行第二步操作，直至无序部分所有元素遍历完成为止
  
  
  
  
  如上依次操作即可。
  当待排序元素为2时，如下
  
  经过排序插入后结果为如下：
  
  可见经排序后，两个 2 的相对次序保持不变，说明直接插入排序是稳定的。

4.代码

public class TestSort {/*** 直接插入排序：* 时间复杂度：*            最坏情况下：O(N^2)  逆序的*            最好情况下：O(N)  有序     如果 以后 数据量不大  而且基本上 趋于有序【优化】* 空间复杂度：O(1)* 稳定性：稳定** 一个本身就稳定的排序，一定也可以实现为不稳定的** 但是本身就是不稳定的排序，你能把它变为稳定的排序吗？** @param array*/public static void insertSort(int[] array) {for (int i = 1; i < array.length; i++) {int tmp = array[i];int j = i-1;for (; j >= 0; j--) {//>=if(array[j] > tmp) {array[j+1] = array[j];}else {//array[j+1] = tmp;break;//}}array[j+1] = tmp;}}public static void main(String[] args) {int[] array = {1,5,2,7,9,6,5,7};System.out.println("排序前："+Arrays.toString(array));insertSort(array);System.out.println("排序后："+Arrays.toString(array));}
}

5.总结

时间复杂度：

1. 最坏情况下：O(n^2)
2. 最好情况下：O(n) 有序情况下

空间复杂度： O(1)
稳定性： 稳定

二、希尔排序

1.简介

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

2.过程

3.代码

import java.util.Arrays;
import java.util.Random;
import java.util.Stack;public class TestSort {/***** @param array* @param gap*/public static void shell(int[] array,int gap) {for (int i = gap; i < array.length; i++) {int tmp = array[i];int j = i-gap;for (; j >= 0; j-=gap) {//>=if(array[j] > tmp) {array[j+gap] = array[j];}else {//array[j+1] = tmp;break;//}}array[j+gap] = tmp;}}/*** 时间复杂度：** 空间复杂度：* O(1)* 稳定性：* 不稳定* @param array*/public static void shellSort(int[] array) {int gap = array.length;//10while (gap > 1) {gap /= 2;shell(array,gap);}shell(array,1);}public static void main(String[] args) {int[] array = {1,5,2,7,9,6,5,7};System.out.println("排序前："+Arrays.toString(array));shellSort(array);System.out.println("排序后："+Arrays.toString(array));}
}

4.总结

1.希尔排序是对直接插入排序的优化。
2.当gap > 1时都是预排序，目的是让数组更接近于有序。当gap ==1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
3.希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度: O(N^1.3)
O(N^2)
4. **空间复杂度：**O(1)
5. 稳定性: 不稳定

三、选择排序

1.简介

每一次 **从待排序的数据元素**中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

2.代码

import java.util.Arrays;
import java.util.Random;
import java.util.Stack;public class TestSort {/*** 选择排序：* 时间复杂度：O(N^2)* 空间复杂度：O(1)* 稳定性： 不稳定* @param array*/public static void selectSort(int[] array) {for(int i=0;ifor(int j=i+1;jif(array[j]swwap(array,i,j);}}}}public static void selectSort2(int[] array) {for(int i=0;iint minIndex=i;//记录 最小值的下标int j=i+1;for(;jif(array[j]minIndex=j;}}swwap(array,i,minIndex);}}public static void swap(int[] array,int i,int j){int temp=array[i];array[i]=array[j];array[j]=temp;}public static void main(String[] args) {int[] array = {1,5,2,7,9,6,5,7};System.out.println("排序前："+Arrays.toString(array));selectSort(array);System.out.println("排序后："+Arrays.toString(array));}
}

3.总结

时间复杂度： O(n^2)

空间复杂度： O(1)

稳定性： 不稳定

四、堆排序

1.代码

import java.util.Arrays;
import java.util.Random;
import java.util.Stack;public class TestSort {/*** 堆排序* 时间复杂度：O(n*logn)  和数据有序无序无关* 空间复杂度：O(1)* 稳定性：不稳定* @param array*/public static void heapSort(int[] array) {//1、大根堆 O(N)createHeap(array);//2、排序O(n*logn)int end = array.length-1;while (end > 0) {swap(array,0,end);shiftDown(array,0,end);//向下调整大根堆end--;}}private static void createHeap(int[] array) {for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {shiftDown(array,parent,array.length);}}private static 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,child,parent);parent = child;child = 2*parent+1;}else {break;}}}public static void swap(int[] array,int i,int j){int temp=array[i];array[i]=array[j];array[j]=temp;}public static void main(String[] args) {int[] array = {1,5,2,7,9,6,5,7};System.out.println("排序前："+Arrays.toString(array));heapSort(array);System.out.println("排序后："+Arrays.toString(array));}
}

2.总结

时间复杂度： O(n*logn) 和数据有序无序无关

空间复杂度： O(1)

**稳定性：**不稳定

五、冒泡排序

1.过程

2.代码

import java.util.Arrays;
import java.util.Random;
import java.util.Stack;public class TestSort {/*** 冒泡排序* 不针对优化：* 时间复杂度：O(N^2)* 空间复杂度：O(1)* 稳定性：稳定* @param array*/public static void bubbleSort(int[] array) {for (int i = 0; i < array.length-1; i++) {//boolean flg = false;for (int j = 0; j < array.length-1-i; j++) {if(array[j] > array[j+1]) {swap(array,j,j+1);//flg = true;}}//if(flg == false) {//    break;//}}}public static void main(String[] args) {int[] array = {1,5,2,7,9,6,5,7};System.out.println("排序前："+Arrays.toString(array));bubbleSort(array);System.out.println("排序后："+Arrays.toString(array));}
}

3.总结

时间复杂度： O(N^2)

空间复杂度： O(1)

稳定性： 稳定

六、快速排序

1.简介

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为∶任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右子序列重复该过程，直到所有元素都排列在相应位置上为止。将区间按照基准值划分为左右两半部分的常见方式有:

1. hoare版本
2. 挖坑法
3. 前后指针版本

分而治之的思想，它的排序过程是一个递归调用的过程。

2.过程

一趟排序过程如下,

从上图可以看到，完整的快速排序是建立在一趟快速排序之上的，它的具体步骤如下：

1. 首先对待排序序列进行一趟快速排序；
2. 一趟排序下来之后，基准元素（如30)的左边都是比它小的元素，右边都是比它大的元素；
3. 再对基准元素左边的序列进行快速排序，对右边也进行快速排序；
4. 重复步骤2、3，直到序列排序完成。

3.两种优化快速排序的思想

1.三数取中
面对完全有序的数组，快速排序每趟排序后，key的位置都在边缘，每层递归都只能固定一个数，时间复杂度变成了O(N^2)。

面对这种情况，我们可以在取key时动手脚。每次取key我们不再只取最左或最右的值。而是对比最左、最右、中间的三个元素，取三个元素中，值在另外两者中间的元素作为key。这样，就打乱了有序数组，大大加快了快速排序在面对这种情况时的速度。

2.小区间优化
快速排序对一个元素不多的数组排序，仍需要进行多次递归调用，我们知道递归是比较消耗资源的，所以为了避免在快速排序递归的最后几层大量调用函数，我们可以在数组元素较少时不再递归，而是采用直接插入排序替代，这样就能在不损失多少速度的情况下减少大量的递归次数，达到优化速度的目的。

4.代码-递归、非递归、优化

```java
import java.util.Arrays;
import java.util.Random;
import java.util.Stack;public class TestSort {/*** 快速排序：** 时间复杂度：*     最好情况：O(n*logn)  可以每次 尽量将待排序序列 均匀的分割*     最坏情况：O(n^2)  正序  逆序* 空间复杂度：*    最好情况：O(logn)*    最坏情况：O(N)**  稳定性：不稳定的排序** @param array*/public static void quickSort1(int[] array) {quick(array,0,array.length-1);}/*** 三数取中法* @param array* @param left* @param right* @return 三个数中的 中间数字的下标*/private static int threeMid(int[] array,int left,int right) {int mid = (left+right) >>> 1;if(array[left] < array[right]) {if(array[mid] < array[left]) {return left;}else if(array[mid] > array[right]) {return right;}else {return mid;}}else {// array[left] > array[right]if(array[mid] < array[right]) {return right;}else if(array[mid] > array[left]) {return left;}else {return mid;}}}/**** @param array*/private static void insertSort2(int[] array,int start,int end) {for (int i = start+1 ; i <= end; i++) {int tmp = array[i];int j = i-1;for (; j >= start; j--) {//>=if(array[j] > tmp) {array[j+1] = array[j];}else {//array[j+1] = tmp;break;//}}array[j+1] = tmp;}}private static void quick(int[] array,int start,int end) {if(start >= end) {return;}//递归到小区间时，插入排序if(end-start+1 <= Constant.INSERT_SIZE) {//插入排序insertSort2(array, start, end);return;}//三数取中法-》start  end  mid 找到中间的数字//有序数据下的优化int index = threeMid(array,start,end);swap(array,index, start);int pivot = partition(array,start,end);quick(array,start,pivot-1);quick(array,pivot+1,end);}/*** 快速排序：非递归实现* @param array*/public static void quickSort(int[] array) {Stack stack = new Stack<>();int start = 0;int end = array.length-1;int pivot = partition(array,start,end);//左边有2个元素及以上if(pivot > start+1) {stack.push(start);stack.push(pivot-1);}//右边有2个元素及以上if(pivot < end-1) {stack.push(pivot+1);stack.push(end);}while (!stack.empty()) {end = stack.pop();start = stack.pop();pivot = partition(array,start,end);//左边有2个元素及以上if(pivot > start+1) {stack.push(start);stack.push(pivot-1);}//右边有2个元素及以上if(pivot < end-1) {stack.push(pivot+1);stack.push(end);}}}/*** 一次划分函数* @param array* @param left* @param right* @return*/private static int partition(int[] array,int left,int right) {int tmp = array[left];while (left < right) {//1 2 3 4 5while (left < right && array[right] >= tmp) {right--;}//右边 找到小于tmp的数据array[left] = array[right];while (left < right && array[left] <= tmp) {left++;}//右边 找到小于tmp的数据array[right] = array[left];}array[left] = tmp;return left;}public static void main(String[] args) {int[] array = new int[10_0000];Random random = new Random();for (int i = 0; i < array.length; i++) {array[i] = i;//array[i] = random.nextInt(10_0000);}long startTime = System.currentTimeMillis();quickSort(array);long endTimes = System.currentTimeMillis();System.out.println(endTimes-startTime);}
}

public class Constant {public static final int INSERT_SIZE = 100;
}

5.总结

时间复杂度：

• 最坏情况下：有序：O(n^2)
• 最好情况下：O(n*logn) 尽量将待排序序列均匀分割

空间复杂度：

• 最坏情况下：O(n)
• 最好情况下：O(logn)

稳定性： 不稳定

七、归并排序

1.简介

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide andConquer)的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列;即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序核心步骤:

2.过程

3.代码

1.递归

/*** 归并排序* 时间复杂度：n*logn    不管有序还是无序* 空间复杂度：O(N)* 稳定性：稳定** 冒泡   插入  归并* @param array*/public static void mergeSort(int[] array) {mergeSortFunction(array,0,array.length-1);}private static void mergeSortFunction(int[] array,int low,int high) {if(low >= high) {return;}int mid = (low+high) >>> 1;mergeSortFunction(array,low,mid);mergeSortFunction(array,mid+1,high);merge(array,low,high,mid);}/*** 实现这个合并函数* @param array* @param low* @param high* @param mid*/private static void merge(int[] array,int low,int high,int mid) {int[] tmp = new int[high-low+1];int k = 0;int s1 = low;int e1 = mid;int s2 = mid+1;int e2 = high;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++];}for (int i = 0; i < k; i++) {array[i+low] = tmp[i];}}

2.非递归

    /*** 归并排序 ：非递归* @param array*/public static void mergeSort2(int[] array) {int gap = 1;while (gap < array.length) {for (int i = 0; i < array.length; i += gap*2 ) {int low = i;int mid = low+gap-1;if(mid >= array.length) {mid = array.length-1;}int high = mid+gap;if(high >= array.length) {high = array.length-1;}merge(array,low,high,mid);}gap = gap*2;}}

海量数据排序问题

概念

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

过程

1. 先把文件切分成200份，每个512 M
2. 分别对512M排序，因为内存已经可以放的下，所以任意排序方式都可以
3. 200份文件进行2路归并，同时对200份有序文件做归并过程，最终结果就有序了