排序的概念
排序：所谓排序，就是使⼀串记录，按照其中的某个或某些关键字的⼤⼩，递增或递减的排列起来的
插入排序
基本思想
直接插⼊排序是⼀种简单的插⼊排序法，其基本思想是：把待排序的记录按其关键码值的⼤⼩逐个插⼊到⼀个已经排好序的有序序列中，直到所有的记录插⼊完为⽌，得到⼀个新的有序序列 。
实际中我们玩扑克牌时，就⽤了插⼊排序的思想
直接插入排序
当插⼊第 i(i>=1) 个元素时，前⾯的 array[0],array[1],…,array[i-1] 已经排好序，此时⽤ array[i] 的排序码与 array[i-1],array[i-2],… 的排序码顺序进⾏⽐较，找到插⼊位置即将 array[i] 插⼊，原来位置上的元素顺序后移
实现
void Insertsort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int c = i;int temp = a[c+1];while (c >= 0){if (a[c]>temp){a[c+1] = a[c];c--;}elsebreak;//从小到大排,前面已经排好了}a[c + 1] = temp;}
}特点:
时间复杂度:O(N^2)
空间复杂度:O(1)
稳定性:稳定
适用场景:基本有序的情况或者数据量小
希尔排序
上面的直接插入,我们会发现,如果是在一个逆序的数据中,效率并不高,那是否可以对其先进行预排序,,再进行插入呢?
此时就是希尔排序
希尔排序法⼜称缩⼩增量法。希尔排序法的基本思想是：先选定⼀个整数（通常是gap = n/3+1），把 待排序⽂件所有记录分成各组，所有的距离相等的记录分在同⼀组内，并对每⼀组内的记录进⾏排 序，然后gap=gap/3+1得到下⼀个整数，再将数组分成各组，进⾏插⼊排序，当gap=1时，就相当于 直接插⼊排序。它是在直接插⼊排序算法的基础上进⾏改进⽽来的，综合来说它的效率肯定是要⾼于直接插⼊排序算法的。
动图
总结:
总结:1. 希尔排序是对直接插⼊排序的优化。2. 当 gap > 1 时都是预排序，⽬的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体⽽⾔，可以达到优化的效果。
实现
void ShellSort(int* a, int n)
{int gap = n;while (gap >1){gap = gap / 3+1;for (int i = 0; i < n - gap; i++){int right = i;int temp = a[right + gap];while (right >= 0){if (a[right] > a[right+gap]){a[right + gap] = a[right];right -= gap;}elsebreak;}a[right + gap] = temp;}}
}特点:
时间复杂度:O(N^1.3)左右
空间复杂度:O(1)
稳定性:不稳定
选择排序
选择排序的基本思想：每⼀次从待排序的数据元素中选出最⼩（或最⼤）的⼀个元素，存放在序列的起始位置，直到全部 排序的数据元素排完 。
直接选择排序
1. 在元素集合 array[i]--array[n-1] 中选择关键码最⼤(⼩)的数据元素2. 若它不是这组元素中的最后⼀个(第⼀个)元素，则将它与这组元素中的最后⼀个（第⼀个）元素交换3. 在剩余的 array[i]--array[n-2]（array[i+1]--array[n-1]） 集合中，重复上述步 骤，直到集合剩余 1 个元素
代码实现:
我们会发现要遍历n*n次,效率似乎太慢
如果我们一次选出未被选择区域的最大与最小数,效率可提升部分
下面实现
void SelectSort(int* a, int n)
{int left = 0;int right = n - 1;while (left a[maxi]){maxi = i;}}//必须判断是否,因为有可能出现left与最大值的下标相等的情况,在第一次交换后,maxi对应的max值就不是最大值了if (maxi == left)maxi = mini;swap(&a[left], &a[mini]);swap(&a[right], &a[maxi]);left++;right--;}
} 特点:
时间复杂度 :O(N^2)
空间复杂度:O(1)
稳定性:不稳定
堆排序
在前面已讲
交换排序
冒泡排序
快速排序
快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：任取待排序元素
序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均⼩
于基准值，右⼦序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列
在相应位置上为⽌
快速排序
快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均⼩于基准值，右⼦序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列 在相应位置上为⽌
hoare版本
1.创建左右指针，确定基准值
2.从右向左找出⽐基准值⼩的数据，从左向右找出⽐基准值⼤的数据，左右指针数据交换，进⼊下次 循环
void Quicksort(int* a, int left, int right)
{if (left >= right)return;int keyi = left;int begin = left;int end = right;while (begin < end){while (a[end] >= a[keyi] && end > begin)//加个等于号,那么符合,再减就算end
挖空法
创建左右指针。⾸先从右向左找出⽐基准⼩的数据，找到后⽴即放⼊左边坑中，当前位置变为新 的"坑"，然后从左向右找出⽐基准⼤的数据，找到后⽴即放⼊右边坑中，当前位置变为新的"坑"，结 束循环后将最开始存储的分界值放⼊当前的"坑"中，返回当前"坑"下标（即分界值下标）
void QuickSort1(int* a, int left,int right)
{if (left >= right)return;if (right - left <= 10){InsertSort(a+left, right - left + 1);//起始位置不定return;}else{int key = a[keyi];while (begin < end){while (a[end] >= key && begin < end)end--;a[keyi] = a[end];keyi = end;while (a[begin] <= key && begin < end)begin++;a[end] = a[begin];keyi = begin;}//begin==enda[keyi] = key;QuickSort1(a, left, keyi - 1);QuickSort1(a, keyi + 1, right);}
}
lomuto前后指针
创建前后指针，从左往右找⽐基准值⼩的进⾏交换，使得⼩的都排在基准值的左边。操作
如果cur指针找到了比key值小的数据,那么prev指针就与cur指针的数据交换,然cur++,prev++
void QuickSort2(int* a, int left, int right)
{if (left >= right)return;if (right - left + 1 <= 10){InsertSort(a + left, right - left + 1);//起始位置不定return;}else{int keyi = left;int prev = left;int cur = left + 1;while (cur < right){if (a[right] < a[keyi] && ++prev != cur)swap(&a[prev], &a[cur]);cur++;}keyi = prev;QuickSort2(a, left, keyi - 1);QuickSort2(a, keyi + 1, right);
}