排序算法总结
BitTigerio 2017-12-13
排序算法
文章内公式可能不能解析，可以到我的技术博客的网站进行查阅
- 交流或更多内容请关注我的公众号：nezha_blog
- 我的技术博客：nezha.github.io
冒泡排序
原理
俩俩比较相邻记录的排序码，若发生逆序，则交换；有俩种方式进行冒泡，一种是先把小的冒泡到前边去，另一种是把大的元素冒泡到后边。
性能
时间复杂度为$O(N^2)$，空间复杂度为$O(1)$。排序是稳定的，排序比较次数与初始序列无关，但交换次数与初始序列有关。
优化
若初始序列就是排序好的，对于冒泡排序仍然还要比较$O(N^2)$次，但无交换次数。可根据这个进行优化，设置一个flag，当在一趟序列中没有发生交换，则该序列已排序好，但优化后排序的时间复杂度没有发生量级的改变。
###代码
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
boolean flag = true;
for (int j = arr.length - 1; j > i; j--) {
if (arr[j] < arr[j - 1]) {
int tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
flag = false;
}
}
if (flag) return;
}
}插入排序
原理
依次选择一个待排序的数据，插入到前边已排好序的序列中。
性能
时间复杂度为$O(N^2)$，空间复杂度为$O(1)$。算法是稳定的，比较次数和交换次数都与初始序列有关。
优化
直接插入排序每次往前插入时，是按顺序依次往前找，可在这里进行优化，往前找合适的插入位置时采用二分查找的方式，即折半插入。
折半插入排序相对直接插入排序而言：平均性能更快，时间复杂度降至$O(NlogN)$，排序是稳定的，但排序的比较次数与初始序列无关，总是需要$foor(log(i))+1$次排序比较。
代码
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++){
out:
for (int j=i;j>0;j--){
if (arr[j] < arr[j-1]){
int tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
}else break out;
}
}
}public static void insertBinarySort(int[] arr){
for (int i = 1; i < arr.length; i++){
if (arr[i] < arr[i-1]){
int temp = arr[i];
int low = 0, high = i - 1, mid;
while (low <= high){
mid = (low + high) / 2;
if (temp < arr[mid]){
high = mid - 1;
}else {
low = mid + 1;
}
}
for (int j = i; j >low; j--){
arr[j] = arr[j - 1];
}
arr[low] = temp;
}
}
}希尔排序
原理
插入排序的改进版，是基于插入排序的以下俩点性质而提出的改进方法：
- 插入排序对几乎已排好序的数据操作时，效率很高，可以达到线性排序的效率。
- 但插入排序在每次往前插入时只能将数据移动一位，效率比较低。
所以希尔排序的思想是：
- 先是取一个合适的
gap<n作为间隔，将全部元素分为gap个子序列，所有距离为gap的元素放入同一个子序列，再对每个子序列进行直接插入排序； - 缩小间隔gap，例如去
gap=ceil(gap/2)，重复上述子序列划分和排序 - 直到，最后gap=1时，将所有元素放在同一个序列中进行插入排序为止。
###性能
开始时，gap取值较大，子序列中的元素较少，排序速度快，克服了直接插入排序的缺点；其次，gap值逐渐变小后，虽然子序列的元素逐渐变多，但大多元素已基本有序，所以继承了直接插入排序的优点，能以近线性的速度排好序。
###代码
public static void shellSort(int[] arr) {
int gap = Math.round(arr.length / 2);
while (gap > 0) {
for (int i = 0;i<gap;i++){
for (int j = i + gap;j<arr.length;j+=gap){
if (arr[j] > arr[j-gap]){
int temp = arr[j];
int k = j - gap;
while (k >= 0 && arr[k] > temp)
{
arr[k + gap] = arr[k];
k -= gap;
}
arr[k + gap] = temp;
}
}
}
}
}public static void shellSort2(int[] arr){
for (int gap = arr.length / 2; gap > 0; gap /= 2){
for (int i = 0; i < arr.length; i = i + gap){
int temp = arr[i];
int j;
for (j = i; j >= gap && temp < arr[j-gap]; j -= gap){
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}选择排序
原理
每次从未排序的序列中找到最小值，记录并最后存放到已排序序列的末尾
性能
时间复杂度为$O(N^2)$，空间复杂度为$O(1)$，排序是不稳定的（把最小值交换到已排序的末尾导致的），每次都能确定一个元素所在的最终位置，比较次数与初始序列无关。
代码
public static void selectSort(int[] arr){
int len = arr.length;
//每次从后边选择一个最小值
for (int i = 0; i < len-1; i++){ //只需选择n-1次
int min = i;
for (int j = i+1; j < len; j++){
if (arr[min]>arr[j]){
min = j;
}
}
if (min != i){
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}快速排序
原理
分而治之思想：
- Divide：找到基准元素pivot，将数组A[p..r]划分为A[p..pivotpos-1]和A[pivotpos+1...q]，左边的元素都比基准小，右边的元素都比基准大;
- Conquer：对俩个划分的数组进行递归排序；
- Combine：因为基准的作用，使得俩个子数组就地有序，无需合并操作。
性能
快排的平均时间复杂度为$O(NlogN）$，空间复杂度为$O(logN)$，但最坏情况下，时间复杂度为$O(N^2)$，空间复杂度为$O(N)$；且排序是不稳定的，但每次都能确定一个元素所在序列中的最终位置，复杂度与初始序列有关。
代码
public static void swap(int i, int j, int[] arr) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void sortQuick(int[] quickArray) {
int[] arr = quickArray;
quickSort(0, arr.length - 1, arr);
}
public static void quickSort(int start, int end, int[] arr) {
if (start < end) {
int pivot = arr[start];
int left = start;
int right = end;
while (left != right) {
while (arr[right] >= pivot && left < right) right--;
while (arr[left] <= pivot && left < right) left++;
swap(left, right, arr);
}
arr[start] = arr[left];
arr[left] = pivot;
quickSort(start, left - 1, arr);
quickSort(left + 1, end, arr);
}
}归并排序
原理
归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。先考虑合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
再考虑递归分解，基本思路是将数组分解成left和right，如果这两个数组内部数据是有序的，那么就可以用上面合并数组的方法将这两个数组合并排序。如何让这两个数组内部是有序的？可以再二分，直至分解出的小组只含有一个元素时为止，此时认为该小组内部已有序。然后合并排序相邻二个小组即可。
性能
时间复杂度总是为$O(NlogN)$，空间复杂度也总为为4O(N)$，算法与初始序列无关，排序是稳定的。
###代码
public static void mergeSort(int[] arr){
mergeSortDiv(arr,0,arr.length-1);
}
public static int[] mergeSortDiv(int[] arr,int low,int high){
int mid = (low + high) / 2;
if (low < high) {
// 左边
mergeSortDiv(arr, low, mid);
// 右边
mergeSortDiv(arr, mid + 1, high);
// 左右归并
merge(arr, low, mid, high);
}
return arr;
}
public static void merge(int[] nums, int low, int mid, int high){
int[] temp = new int[high - low + 1];
int i = low;// 左指针
int j = mid + 1;// 右指针
int k = 0;
// 把较小的数先移到新数组中
while (i <= mid && j <= high) {
if (nums[i] < nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
// 把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = nums[i++];
}
// 把右边边剩余的数移入数组
while (j <= high) {
temp[k++] = nums[j++];
}
// 把新数组中的数覆盖nums数组
for (int k2 = 0; k2 < temp.length; k2++) {
nums[k2 + low] = temp[k2];
}
}堆排序
原理
堆排序在 top K 问题中使用比较频繁。堆排序是采用二叉堆的数据结构来实现的，虽然实质上还是一维数组。二叉堆是一个近似完全二叉树 。
二叉堆具有以下性质：
- 父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
- 每个节点的左右子树都是一个二叉堆（都是最大堆或最小堆）。
步骤：
构造最大堆（Build_Max_Heap）：若数组下标范围为0~n，考虑到单独一个元素是大根堆，则从下标n/2开始的元素均为大根堆。于是只要从n/2-1开始，向前依次构造大根堆，这样就能保证，构造到某个节点时，它的左右子树都已经是大根堆。
堆排序（HeapSort）：由于堆是用数组模拟的。得到一个大根堆后，数组内部并不是有序的。因此需要将堆化数组有序化。思想是移除根节点，并做最大堆调整的递归运算。第一次将heap[0]与heap[n-1]交换，再对heap[0...n-2]做最大堆调整。第二次将heap[0]与heap[n-2]交换，再对heap[0...n-3]做最大堆调整。重复该操作直至heap[0]和heap[1]交换。由于每次都是将最大的数并入到后面的有序区间，故操作完后整个数组就是有序的了。
最大堆调整（Max_Heapify）：该方法是提供给上述两个过程调用的。目的是将堆的末端子节点作调整，使得子节点永远小于父节点 。
性能
时间复杂度为$O(NlogN)$，空间复杂度为$O(1)$，因为利用的排序空间仍然是初始的序列，并未开辟新空间。算法是不稳定的，与初始序列无关。
使用场景
想知道最大值或最小值时，比如优先级队列，作业调度等场景。
代码
排序算法之归并排序(JAVA)-数组形式
计数排序
原理
先把每个元素的出现次数算出来，然后算出该元素所在最终排好序列中的绝对位置(最终位置)，再依次把初始序列中的元素，根据该元素所在最终的绝对位置移到排序数组中。
性能
时间复杂度为O(N+K)，空间复杂度为O(N+K)，算法是稳定的，与初始序列无关，不需要进行比较就能排好序的算法。
桶排序
原理
- 根据待排序列元素的大小范围，均匀独立的划分M个桶
- 将N个输入元素分布到各个桶中去
- 再对各个桶中的元素进行排序
- 此时再按次序把各桶中的元素列出来即是已排序好的。
性能
时间复杂度为$O(N+C)$，$O(C)=O(M(N/M)log(N/M))=O(NlogN-NlogM)$，空间复杂度为$O(N+M)$，算法是稳定的，且与初始序列无关。
使用场景
算法思想和散列中的开散列法差不多，当冲突时放入同一个桶中；可应用于数据量分布比较均匀，或比较侧重于区间数量时。
基数排序
原理
对于有d个关键字时，可以分别按关键字进行排序。有俩种方法：
- MSD：先从高位开始进行排序，在每个关键字上，可采用计数排序
- LSD：先从低位开始进行排序，在每个关键字上，可采用桶排序
性能
时间复杂度为O(d*(N+K))，空间复杂度为O(N+K)。
总结
参考文献
[1]经典排序算法总结与实现-基于Python的排序算法总结，写的很不错
[2]排序算法总结-带有优化
