好久不见~
1.概念
排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。 平时的上下文中，如果提到排序，通常指的是排升序。 通常意义上的排序，都是指的原地排序。
1.1稳定性
两个相等的数据，如果经过排序后，排序算法能保证其相对位置不发生变化，则我们称该算法是具备稳定性的排序算法。（即相同元素相对位置改变前的元素与相对位置改变后的前后顺序应该保持一致性）
一个稳定的排序，可以实现为不稳定的排序但是一个本身就不稳定的排序，是不可以变成稳定的排序的
如下图所示 ：
2.七大排序
2.1插入排序
2.1.1直接插入排序**-**原理
原理：
整个区间被分为： 有序区间 ，无序区间
每次选择无序区间的第一个元素，在有序区间内选择合适的位置插入
解题思路：
①找到一个临时储存点tmp,将每次无序区间的第一个用下标i记做的元素放入。
②利用另一个变量j来进行判断与tmp所代表的元素的大小。
③设置终止循环条件直至j<0
代码如下：
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; 只要j回退的时候，遇到了 比tmp小的元素就结束这次的比较
break;
}
}
//j回退到了 小于0 的地方
array[j+1] = tmp;
}
}
**2.1.2性能分析 **
最好平均最坏时间复杂度O(N)O(N²）O(N²）空间复杂度O(1)O(1)O(1)稳定性稳定稳定稳定
2.1.3折半插入排序（了解）
原理：
利用折半查找的思想来进行排序
解题思路：
①每次循环将left的值定为0，right的值定为i
②折中判断两者中间的坐标所代表的值与被判断值的大小关系
③若array[mid]<被判断值，left=mid+1;反之，array[mid]>被判断值，right=mid(目的是找到比array[mid]大的值与其进行对换）
代码如下：
public static void bsInsertSort(int[] array) { for (int i = 1; i < array.length; i++) { int v = array[i]; int left = 0; int right = i; // [left, right) // 需要考虑稳定性 while (left < right) { int m = (left + right) / 2; if (v > array[m]) { left = m + 1; } else { right = m-1; } } // 搬移 for (int j = i; j > left; j--) { array[j] = array[j - 1]; } array[left]=v; } }
2.2**希尔排序 **
2.2.1原理
原理：
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有
距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时， 所有记录在统一组内排好序。
希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很 快。这样整体而言，可以达到优化的效果
解题思路：(主体将其分为几个部分，每个部分进行各自的递归）
①找到增量的取值的问题，在求解具体问题时，不易保证是质数，因此常gap/=2的方式进行求解
②实际上就是一个之间插入排序，只不过将直接排序中的j=i-1的下标值更替为j=i-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 { break; } } array[j+gap] = tmp; } } public static void shellSort(int[] array) { int gap = array.length; while (gap > 1) { shell(array,gap); gap /= 2; } shell(array,1);//保证最后是1组 }
2.2.2性能分析
类型对应参数时间复杂度O(N的1.3次方~N的1.5次方）空间复杂度O(1)稳定性不稳定
2.3选择排序
2.3.1原理
原理：
每一次从无序区间选出最大（或最小）的一个元素，存放在无序区间的最后（或最前），直到全部待排序的数据元素排完 。
解题思路：
①实际上就是两两比较大小进行交换，最后成为有序序列的过程
②优化后的代码实际上是每趟直接找出最小值的下标，并与i值的下标进行直接交换
代码分析：
public static void swap(int a,int b){ int tmp=a; a=b; b=tmp; } //选择排序:不稳定的排序 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]){ swap(array[i],array[j]); } } } }//以下为优化好后的代码，此处的优化，指的是交换次数的变化，而时间复杂度并为更改 public static void selectSort1(int []array){ for(int i=0;i<array.length;i++){ //将最小值的下标记录下来，而i在交换中只需要与这个最小值进行比较 int minSize=i; for(int j=i+1;j<array.length;j++){ if(array[j]<array[minSize]){ minSize=j; } }swap(array[i],array[minSize]); }
2.3.2性能分析
类型对应参数时间复杂度O(N²）空间复杂度O(1)稳定性不稳定
2.4堆排序（在上一节堆中有详细的讲解）
2.4.1原理
原理：
基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大的数，而是通过堆来选择无序区间的最大的数。
解题思路：
①建堆（建大根堆）
②交换向下进行调整
代码如下：
public static void heapSort(int []array){ createHeap(array); int end=array.length-1; while(end>0){ swap(array[0],array[end]); shiftDown(array,0,end); end--; } } public static void createHeap(int[]array){ for(int parent=(array.length-1-1)/2;parent>=0;parent--){ shiftDown(array,parent,array.length); } }//向下调整 public 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],array[parent]); parent=child; child=2*parent+1; }else{ break; } } }
2.4.2性能分析
类型对应参数时间复杂度O(N * log N)空间复杂度O(1)稳定性不稳定
2.5冒泡排序
2.5.1原理
原理：
在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序
解题思路：
①利用j来比较每趟中的大小，每趟结束最大的沉入最下面
②利用i来表示趟数
③优化代码加入flg=false,用来确保没有交换后直接跳出循环来，进而节省时间
代码分析：
//冒泡排序(稳定的排序。时间复杂度为n²，在排好序的情况下时间复杂度为n,空间复杂度为O(1) public static void bubblesort(int array[]){ boolean flg=false; 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]){ swap(array[j],array[j+1]); flg=true; } } if(flg=false){ break; } } }
2.5.2性能分析
类型对应参数时间复杂度O(N²)空间复杂度O(1)稳定性稳定
原理：
从待排序区间选择一个数，作为基准值(pivot)；
Partition: 遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可 以包含相等的）放到基准值的右边；
采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 == 1，代表已经有序，或者小区间 的长度 == 0，代表没有数据。
解题思路：
①找基准，以基准为分界线，基准左边的值若大于基准，则换到右边的空位，若小于基准则start++;基准右边的值若小于基准，则换到左边的空位，若大于，则end--;
②分别对各个部分进行递归
代码如下1：(这里展示的是挖坑法）
//快速排序 public static void quickSort(int []array){ quick(array,0,array.length-1); } public static void quick(int []array,int left,int right){ if(left>=right){ return ; }//找基准 int pivot=patition(array,left,right); //递归左边的 quick(array,left,pivot-1); //递归右边的 quick(array,pivot+1,right); } public static int patition(int []array,int start,int end) { int tmp = array[start]; while (start < end) { while (start < end && array[end] >= tmp) { end--; }//end下标遇到了小于tmp的值 array[start] = array[end]; while (start < end && array[start] <= tmp) { start++; }//start下标遇到了大于tmp的值 array[end] = array[start]; }//当start=end时 array[start]=tmp; return start; }解题思路2：
①找基准
②找到基准后，基准两侧同时进行挖坑法的步骤②，两边找到一大一小则直接进行位置的交换
代码2：（Hoare法）
private static int partition(int[] array, int left, int right) { int i = left; int j = right; int pivot = array[left]; while (i < j) { while (i < j && array[j] >= pivot) { j--; } while (i < j && array[i] <= pivot) { i++; } swap(array, i, j); } swap(array, i, left); return i; }
类型对应参数时间复杂度O(KNlogn)
O(N^2)空间复杂度O(logN)O（N）稳定性不稳定
关于快速排序优化，以及剩下的归并排序将会在下节出现~~~
版权归原作者 反内码者 所有， 如有侵权，请联系我们删除。