1.基本概念
1.1排序的稳定性（重要）
两个相等的数据，如果经过排序后，排序算法能保证其相对位置不发生变化，则我们称该算法是具备稳定性的排序算法。
（经验）如果当前这个排序，在排序的过程中没有发生跳跃式的交换，那么我们认为这个排序是稳定的排序，比如堆排，就是不稳定的。稳定的排序也可被实现为不稳定的排序，但不稳定的则不可以变成稳定的排序。
现实生活中的应用
2.常用排序总览
3.插入排序
3.1直接插入排序-原理
整个区间被分为
- 有序区间
- 无序区间
每次选择无序区间的第一个元素，在有序区间内选择合适的位置插入
确定下标i，来遍历数组的元素，那么下标i从几开始呢，从数组的·1一位置开始，因为第一个数它肯定是有序的，再来一个下标j，j=i-1，再定义一个tmp，把当前下标的值（i下标）放到tmp中，如果j下标的值大于tmp中的值，将j下标的值放到i位置，j–，此时j<0,0位置没有元素，就将tmp放到0位置（这就成为了一个有序区间）这是第一次直接插入排序的过程，接下来我们上代码。
3.2实现
//稳定性：稳定
//时间复杂度：最坏：数据逆序o（n^2） 最好：数据有序可以达到o(n)
//所以对于直接插入排序，数据越有序越快
import java.util.Arrays;
public class dSort {
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 {
break;
}
}
array[j+1]=tmp;
}
}
public static void main(String[] args) {
int[] arr={2,5,6,8,5};
insertSort(arr);
System.out.println(Arrays.toString(arr));
}
}
对于直接插入排序我们上面总结的结论，会经常遇见这样的问题：当前有一组待排序序列，但是这组待排序序列大部分是有序的请问下面那个排序最适合，对于这样的问题，不要犹豫，选直接插入排序。
另外：直接插入排序一般也会用在一些排序的优化上，例如快排，当数据越来越有序时，就可以进行更好的优化。
性能分析
4.希尔排序（了解）
说一句：如果是面试，你可以跳过希尔排序
4.1希尔排序-原理
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有记录分成个组，所有距离为gap的记录分在同一组内，并对每一组内的记录进行排序。然后，取增量，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。
- 希尔排序是对直接插入排序的优化
- 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
4.2实现
//稳定性：不稳定
//时间复杂度：最坏：o（n^2） 平均：o(n^1.3) 最坏：o（n^2）
//是对直接插入排序的优化
import java.util.Arrays;
public class shellSort {
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=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};//增量数组,取值要求，没有除1之外的公因子，且最后一个增量值必须为1
for (int i = 0; i < drr.length; i++) {
shell(array,drr[i]);
}
}
public static void main(String[] args) {
int[] arr={2,5,6,8,7,23,21,32,43,54,43,2,13,4,34,65,7,6,90};
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
}
4.3性能分析
5.选择排序
5.1直接选择排序-原理
每一次从无序区间选出最大（或最小）的一个元素，存放在无序区间的最后（或最前），直到全部待排序的数据元素排完 。
5.2实现
import java.util.Arrays;
public class selectSort {
public static void selectSort(int []array){
for (int i = 0; i < array.length-1; i++) {
int max=0;
for (int j = i+1; j <array.length;j++) {
if(array[i]>array[j]){//交换
max=array[j];
array[j]=array[i];
array[i]=max;
}
}
}
}
public static void main(String[] args) {
int []arr={2,3,5,7,8,9,13};
selectSort(arr);
System.out.println(Arrays.toString(arr));
}
}
5.3性能分析
其实关于选择排序还有双向选择排序，但由于少用到，在此我们不再描写，感兴趣的朋友可以自行了解。
6.堆排序
6.1堆排序-原理
基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大的数，而是通过堆来选择无序区间的最大的数。
注意： 排升序要建大堆；排降序要建小堆。
关于具体实现过程以及原理请看此篇文章
6.2实现
6.21建大堆
/**
* 调整为大顶堆
* @param arr 待调整的数组
* @param parent 当前父节点的下标
* @param length 需要对多少个元素进行调整
*/
import java.util.Arrays;
public class heapSort {
//首先我们先完成大堆的构建
private static void adjustHeap(int[] arr, int parent, int length){
//临时保存父节点
int temp = arr[parent];
//左子节点的下标
int child = 2 * parent + 1;
//如果子节点的下标大于等于当前需要比较的元素个数，则结束循环
while(child < length){
//判断左子节点和右子节点的大小,若右边大，则把child定位到右边
if(child + 1 < length && arr[child] < arr[child + 1]){
child ++;
}
//若child大于父节点，则交换位置，否则退出循环
if(arr[child] > temp){
//父子节点交换位置
arr[parent] = arr[child];
//因为交换位置之后，不能保证当前的子节点是它子树的最大值，所以需要继续向下比较，
//把当前子节点设置为下次循环的父节点，同时，找到它的左子节点，继续下次循环
parent = child;
child = 2 * parent + 1;
}else{
//如果当前子节点小于等于父节点，则说明此时的父节点已经是最大值了，
//因此无需继续循环
break;
}
}
//把当前节点值替换为最开始暂存的父节点值
arr[parent] = temp;
}
private static void createHeap(int []arr){
for (int i = arr.length/2-1; i >=0 ; i--) {
adjustHeap(arr,i,arr.length);
}
}
public static void main(String[] args) {
int []arr={4,1,9,3,7,8,5,6,2};
createHeap(arr);
System.out.println(Arrays.toString(arr));
}
}
6.22堆排序（不稳定）
堆排序就是利用大顶堆或者小顶堆的特性来进行排序的
基本思想：
把当前数组构建成一个大顶堆。
此时，根节点肯定是所有节点中最大的值，让它和末尾元素交换位置，则最
后一个元素就是最大值。
把剩余的 n - 1个元素重新构建成一个大顶堆，就会得到 n-1 个元素中的最大
值。重复执行此动作，就会把所有的元素调整为有序了。
import java.util.Arrays;
public class dSort {
private static void adjustHeap(int[] arr, int parent, int length){
//临时保存父节点
int temp = arr[parent];
//左子节点的下标
int child = 2 * parent + 1;
//如果子节点的下标大于等于当前需要比较的元素个数，则结束循环
while(child < length){
//判断左子节点和右子节点的大小,若右边大，则把child定位到右边
if(child + 1 < length && arr[child] < arr[child + 1]){
child ++;
}
//若child大于父节点，则交换位置，否则退出循环
if(arr[child] > temp){
//父子节点交换位置
arr[parent] = arr[child];
//因为交换位置之后，不能保证当前的子节点是它子树的最大值，所以需要继续向下比较，
//把当前子节点设置为下次循环的父节点，同时，找到它的左子节点，继续下次循环
parent = child;
child = 2 * parent + 1;
}else{
//如果当前子节点小于等于父节点，则说明此时的父节点已经是最大值了，
//因此无需继续循环
break;
}
}
//把当前节点值替换为最开始暂存的父节点值
arr[parent] = temp;
}
private static void createHeap(int []arr){
for (int i = arr.length/2-1; i >=0 ; i--) {
adjustHeap(arr,i,arr.length);
}
}
//堆排，大堆，升序
private static void heapSort(int []arr){
createHeap(arr);
//循环执行以下操作：1.交换堆顶元素和末尾元素 2.重新调整为大顶堆
for (int i = arr.length-1; i >0; i--) {
int tmp=arr[i];
//将堆顶最大的元素与末尾元素互换，则数组中最后的元素变为最大值
arr[i]=arr[0];
arr[0]=tmp;
//从堆顶开始重新调整结构，使之成为大顶堆
// i代表当前数组需要调整的元素个数，是逐渐递减
adjustHeap(arr,0,i);
}
}
public static void main(String[] args) {
int []arr={4,1,9,3,7,8,5,6,2};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
}
6.3性能分析
7.冒泡排序
7.1冒泡排序-原理
在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序
7.2实现
public class bubbleSort {
public static void bubbleSort(int[]arr){
for (int i = 0; i < arr.length; i++) {
boolean flag=false;
for (int j = 0; j <arr.length-i-1 ; j++) {
//此处你可能会疑问的j<n-i-1，因为冒泡是把每轮循环中较大的数飘到后面，
// 数组下标又是从0开始的，i下标后面已经排序的个数就得多减1，总结就是i增多少，j的循环位置减多少
if (arr[j] > arr[j+1]) {//即这两个相邻的数是逆序的，交换
int tmp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=tmp;
flag=true;
}
}
if(!flag){
break;//没有数据交换，数组已经有序，退出排序
}
}
}
public static void main(String[] args) {
int []arr={4,1,9,3,7,8,5,6,2};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
}
}
7.3性能分析
8.快速排序（重要）
8.1快排-原理
- 从待排序区间选择一个数，作为基准值(pivot)；
- Partition: 遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可
以包含相等的）放到基准值的右边； - 采用分治思想(均匀划分效率最高)，对左右两个小区间按照同样的方式处理，直到小区间的长度 = = 1，代表已经有序，或者小区间的长度 = = 0，代表没有数据。
8.21实现（递归版本）
//稳定性：不稳定
import java.util.Arrays;
public class quickSort {
//找基准
public static int pivot(int[]array,int start,int end){
int tmp=array[start];
while(start<end){
while(start<end&&array[end]>=tmp){
end--;
}
//以下注释掉的代码是可以优化的
//if(start>=end){
// array[start]=tmp;
//break;
//}else{
array[start]=array[end];
//}
//把end的值赋给start
while(start<end&&array[start]<=tmp){
start++;
}
//把start下标的值赋给end
// if(start>=end){
// array[start]=tmp;
// break;
//}else{
array[end]=array[start];
//}
}
array[start]=tmp;
return start;
}
public static void quickSort(int []array,int low,int high){
//递归，递归树的高度logn，最好o(n^2)
//最好 时间复杂度o(nlogn)
if(low<high){
int piv=pivot(array,low,high);
quickSort(array,low,piv-1);
quickSort(array,piv+1,high);
}
}
public static void main(String[] args) {
int []array={2,3,4,5,6,7,8,9,12,1,3,14,19};
quickSort(array,0,array.length-1);
System.out.println(Arrays.toString(array));
}
}
8.22实现（非递归版本）
掌握一种即可（递归与非递归）
//nlog2n 空间复杂度：o(log2n) 最坏：o(n)
public static void quickSort(int []array){
Stack<Integer>stack=new Stack<>();//在堆上，用来存数对，所以不会溢出，并非开辟栈帧的运行栈
int low=0;
int high=array.length-1;
int piv=pivot(array,low,high);
if(piv>low+1){//说明左边有两个数据，并不有序
stack.push(low);
stack.push(piv-1);
}
if (piv<high-1){//说明右边
stack.push(piv+1);
stack.push(high);
}
while(!stack.isEmpty()){
high=stack.pop();//新的high
low=stack.pop();//新的low
piv=pivot(array,low,high);//新基准
if(piv>low+1){//说明左边有两个数据，并不有序
stack.push(low);
stack.push(piv-1);
}
if (piv<high-1){//说明右边
stack.push(piv+1);
stack.push(high);
}
}
}
8.3性能分析
关于快排的时间复杂度代码上不好看出来，我们说的时候就会很模糊。我们下面作分析:递归的时间复杂度：递归的次数*当前遍历的次数，我们把数组看为二叉树，在分析过程中我们就会发现递归次数为二叉树的高度，当前遍历次数大致上可以认为是n。
那么最坏情况是什么情况呢？就是数据有序的时候。，如果给了你1000个数据，而这1000个数据恰好都是有序的，那此时快速排序很明显就不快了，所以接下来我们要做的事情就是优化快速排序！！！
8.4快速排序的优化
选择基准值很重要，有随机选取基准法，具体做法就是随机找到后面的一个下标，然后和low下标的数据交换，最后以low下标交换后的值作为基准，这个方法偶然性比较大，跟人品有关哈哈。所以通常使用三数取中法
import java.util.Arrays;
public class quickSort {
public static int pivot(int[]array,int start,int end){
int tmp=array[start];
while(start<end){
while(start<end&&array[end]>=tmp){
end--;
}
array[start]=array[end];
while(start<end&&array[start]<=tmp){
start++;
}
array[end]=array[start];
}
array[end]=tmp;
return end;
}
public static void swap(int[]array,int i,int j){
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
//三数取中法
public static void medianOfThree(int[]array,int low,int high){
int mid=(low+high)/2;
//array[mid]<=array[low]<=array[high]
if(array[low]<=array[mid]){
swap(array,low,high);
}//array[mid]<=array[low]
if(array[low]>array[high]){
swap(array,low,high);
}//array[low]<=array[high]
if(array[mid]>array[high]){
swap(array,mid,high);
}//array[mid]<=array[high]
}
public static void quickSort(int []array,int low,int high){
if(low<high){
medianOfThree(array,low,high);
//在这之前进行优化
int piv=pivot(array,low,high);
quickSort(array,low,piv-1);
quickSort(array,piv+1,high);
}
}
public static void main(String[] args) {
int []array={2,3,4,5,6,7,8,9,12,1,3,14,19};
quickSort(array,0,array.length-1);
System.out.println(Arrays.toString(array));
}
}
8.41简单对比
10000个数据情况下：优化前107毫秒，（可能情况不同，与设备可能也存在关系）
优化后：85毫秒（可能有误差），但总的来看，是有进步的。
8.5快速排序的另一种优化
待排序区间小于一个阈值时（例如 48），使用直接插入排序，在数据越来越有序的情况下，我们可以使用直接插入排序进行优化。
import java.util.Arrays;
import java.util.Random;
public class quickSort {
public static int pivot(int[]array,int start,int end){
int tmp=array[start];
while(start<end){
while(start<end&&array[end]>=tmp){
end--;
}
array[start]=array[end];
while(start<end&&array[start]<=tmp){
start++;
}
array[end]=array[start];
}
array[end]=tmp;
return end;
}
public static void swap(int[]array,int i,int j){
int tmp=array[i];
array[i]=array[j];
array[j]=tmp;
}
//三数取中法
public static void medianOfThree(int[]array,int low,int high){
int mid=(low+high)/2;
//array[mid]<=array[low]<=array[high]
if(array[low]<=array[mid]){
swap(array,low,high);
}//array[mid]<=array[low]
if(array[low]>array[high]){
swap(array,low,high);
}//array[low]<=array[high]
if(array[mid]>array[high]){
swap(array,mid,high);
}//array[mid]<=array[high]
}
//直接插入排序
public static void insertSortBound(int []array,int low,int high){
for (int i = low+1; i <=high ; i++) {
int tmp=array[i];
int j=i-1;
for(;j>=low;j--){
if(array[j]>tmp){
array[j+1]=array[j];
}else {
break;
}
}
array[j+1]=tmp;
}
}
public static void quickSort(int []array,int low,int high){
if(low>=high) return;
if (high-low+1<=50){
//使用插入排序进行优化
insertSortBound(array,low,high);
return;//这里一定要return，到这说明这个区间范围有序了，直接结束
}
// if(low<high){
medianOfThree(array,low,high);
//在这之前进行优化
int piv=pivot(array,low,high);
quickSort(array,low,piv-1);
quickSort(array,piv+1,high);
// }
}
public static void main(String[] args) {
int[]array=new int[1_0000];
Random random=new Random();
for (int i = 0; i <array.length ; i++) {
array[i]=random.nextInt(1_0000);
}
long startTime=System.currentTimeMillis();
quickSort(array,0,array.length-1);
long endTime=System.currentTimeMillis();
System.out.println((endTime - startTime));
System.out.println(Arrays.toString(array));
}
}
9.归并排序(重要)
9.1归并排序-原理
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
9.2合并两个有序的数组
public static void merge(int []array,int low,int mid,int high) {
int s1=low;//合并的第一段开始 s:start e:end
int e1=mid;//第一段结尾
int s2=mid+1;//第二段开始
int e2=high;//第二段结尾
int []tmp=new int[high-low+1];//数组长度
int k=0;//tmp数组下标
while(s1<=mid&&s2<=high){//保证有数据
if(array[s1]<=array[s2]){
tmp[k++]=array[s1++];
}else{
tmp[k++]=array[s2++];
}
}
//到这有可能第一段或第二段还有数据，
while(s1<=mid){
tmp[k++]=array[s1++];
}
while(s2<=high){
tmp[k++]=array[s2++];
}
for (int i = 0; i <tmp.length ; i++) {
array[i+low]=tmp[i];//防止数据被覆盖
}
}
9.3实现
//时间复杂度：o(nlogn)不论好坏
//空间复杂度;o(n)
//稳定性：稳定
import java.util.Arrays;
public class mergeSort {
public static void merge(int []array,int low,int mid,int high) {
int s1=low;//合并的第一段开始 s:start e:end
int e1=mid;//第一段结尾
int s2=mid+1;//第二段开始
int e2=high;//第二段结尾
int []tmp=new int[high-low+1];//数组长度
int k=0;//tmp数组下标
while(s1<=mid&&s2<=high){//保证有数据
if(array[s1]<=array[s2]){
tmp[k++]=array[s1++];
}else{
tmp[k++]=array[s2++];
}
}
//到这有可能第一段或第二段还有数据，
while(s1<=mid){
tmp[k++]=array[s1++];
}
while(s2<=high){
tmp[k++]=array[s2++];
}
for (int i = 0; i <tmp.length ; i++) {
array[i+low]=tmp[i];//防止数据被覆盖
}
}
public static void mergeSort(int []array,int low,int high){//分解+合并
if(low>=high) return;
int mid=(low+high)/2;
mergeSort(array,low,mid);
mergeSort(array,mid+1,high);
merge(array,0,mid,array.length-1);
}
public static void main(String[] args) {
int []array={1,2,3,4,5,6,7,8,9};
System.out.println(Arrays.toString(array));
}
}
//在排序过程中重复利用两个数组，减少元素的复制过程。可进行优化
- 非递归（了解即可）
import java.util.Arrays;
public class mergeSort {
public static void merge1(int []array,int gap){
int s1=0;//刚开始两两一组
int e1=s1+gap-1;
int s2=e1+1;
int e2=s2+gap-1<array.length?s2+gap-1:array.length-1;//要判断，有可能s2+gap-1之后所在位置没有元素
int []tmp=new int[array.length];
int k=0;//数组下标
//当有两个归并段时
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=e2+1;//分析gap与上面的for循环条件
e1=s1+gap-1;
s2=e1+1;
e2=s2+gap-1<array.length?s2+gap-1:array.length-1;
}
//退出上面循环后
// 把s1段内数据拷贝下来,因为e1有可能已经越界
while(s1<array.length){
tmp[k++]=array[s1++];
}
for (int i = 0; i <tmp.length ; i++) {
array[i]=tmp[i];
}
}
public static void mergeSort(int[]array){
for (int i = 1; i <array.length ; i*=2) {
merge1(array,i);
}
}
public static void main(String[] args) {
int []array={3,4,6,7,8,5,2,4,6,7,8,9};
mergeSort(array);
System.out.println(Arrays.toString(array));
}
}
9.3性能分析
9.4海量数据排序问题
外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序
- 先把文件切分成 200 份，每个 512 M
- 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
- 进行 200 路归并，同时对 200 份有序文件做归并过程，最终结果就有序了
10.总结
版权声明：本文为qq_49425839原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。