排序算法汇总 - milkandbread/summary-interview GitHub Wiki
| 排序算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 是否稳定 |
|---|---|---|---|---|
| 冒泡排序 | O（n2） | O（n2） | O（1） | 是 |
| 选择排序 | O（n2） | O（n2） | O（1） | 不是 |
| 直接插入排序 | O（n2） | O（n2） | O（1） | 是 |
| 归并排序 | O(nlogn) | O(nlogn) | O（n） | 是 |
| 快速排序 | O(nlogn) | O（n2） | O（logn） | 不是 |
| 堆排序 | O(nlogn) | O(nlogn) | O（1） | 不是 |
| 希尔排序 | O(nlogn) | O（ns） | O（1） | 不是 |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | 是 |
| 基数排序 | O(N∗M) | O(N∗M) | O(M) | 是 |
是相邻元素之间的比较和交换，两重循环O(n2)；所以，如果两个相邻元素相等，是不会交换的。所以它是一种稳定的排序方法
void bubble_sort(int array[], int N)
{
//使用冒泡的方式进行排序
for(int i=0;i<N;i++){
for(int j=0;j<N-1-i;j++){
if(array[j]>array[j+1]){
int temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
}
优化一
void bubble_sort(int array[], int N)
{
//使用冒泡的方式进行排序
for(int i=0;i<N;i++){
//有序标记，每一轮的初始值都是true
bool isSorted=true;
for(int j=0;j<N-1-i;j++){
if(array[j]>array[j+1]){
int temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
//因为有元素交换，索引数组还不是有序的，标记变为false
isSorted=false;
}
}
if(isSorted){
break;
}
}
return 0;
}
每个元素都与第一个元素相比，产生交换，两重循环O(n2)；举个栗子，5 8 5 2 9，第一遍之后，2会与5交换，那么原序列中两个5的顺序就被破坏了。所以不是稳定的排序算法
第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；
第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；
以此类推.....
第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，
直到整个序列按关键码有序。
void print(int a[], int n ,int i){
cout<<"第"<<i+1 <<"趟 : ";
for(int j= 0; j<8; j++){
cout<<a[j] <<" ";
}
cout<<endl;
}
/**
* 数组的最小值
*
* @return int 数组的键值
*/
int SelectMinKey(int a[], int n, int i)
{
int k = i;
for(int j=i+1 ;j< n; ++j) {
if(a[k] > a[j]) k = j;
}
return k;
}
/**
* 选择排序
*
*/
void selectSort(int a[], int n){
int key, tmp;
for(int i = 0; i< n; ++i) {
key = SelectMinKey(a, n,i); //选择最小的元素
if(key != i){
tmp = a[i]; a[i] = a[key]; a[key] = tmp; //最小元素与第i位置元素互换
}
print(a, n , i);
}
}
改进法：
void selectSort(int a[],int len) {
int i,j,min,max,tmp;
for(i=0; i<len/2; i++){ // 做不超过n/2趟选择排序
min = max = i;
for(j=i+1; j<=len-1-i; j++){
//分别记录最大和最小关键字记录位置
if(a[j] > a[max]){
max = j;
continue;
}
if(a[j] < a[min]){
min = j;
}
}
//该交换操作还可分情况讨论以提高效率
if(min != i){//当第一个为min值，不用交换
tmp=a[min]; a[min]=a[i]; a[i]=tmp;
}
if(min == len-1-i && max == i)//当第一个为max值，同时最后一个为min值，不再需要下面操作
continue;
if(max == i)//当第一个为max值，则交换后min的位置为max值
max = min;
if(max != len-1-i){//当最后一个为max值，不用交换
tmp=a[max]; a[max]=a[len-1-i]; a[len-1-i]=tmp;
}
print(a,len, i);
}
}
int main(){
int a[8] = {3,1,5,7,2,4,9,6};
cout<<"初始值：";
for(int j= 0; j<8; j++){
cout<<a[j] <<" ";
}
cout<<endl<<endl;
selectSort(a, 8);
print(a,8,8);
}
插入排序是在一个已经有序的小序列的基础上，一次插入一个元素。刚开始这个小序列只包含第一个元素，事件复杂度O(n2)。比较是从这个小序列的末尾开始的。想要插入的元素和小序列的最大者开始比起，如果比它大则直接插在其后面，否则一直往前找它该插入的位置。如果遇见了一个和插入元素相等的，则把插入元素放在这个相等元素的后面。所以相等元素间的顺序没有改变，是稳定的。
void print(int a[], int n ,int i){
cout<<i <<":";
for(int j= 0; j<8; j++){
cout<<a[j] <<" ";
}
cout<<endl;
}
void InsertSort(int a[], int n)
{
for(int i= 1; i<n; i++){
if(a[i] < a[i-1]){ //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
int j= i-1;
int x = a[i]; //复制为哨兵，即存储待排序元素
a[i] = a[i-1]; //先后移一个元素
while(x < a[j]){ //查找在有序表的插入位置
a[j+1] = a[j];
j--; //元素后移
}
a[j+1] = x; //插入到正确位置
}
print(a,n,i); //打印每趟排序的结果
}
}
int main(){
int a[8] = {3,1,5,7,2,4,9,6};
InsertSort(a,8);
print(a,8,8);
}
快速排序有两个方向，左边的i下标一直往右走，当a[i] <= a[center_index]，其中center_index是中枢元素的数组下标，一般取为数组第0个元素。而右边的j下标一直往左走，当a[j] > a[center_index]。如果i和j都走不动了，i <= j, 交换a[i]和a[j],重复上面的过程，直到i>j。 交换a[j]和a[center_index]，完成一趟快速排序。在中枢元素和a[j]交换的时候，很有可能把前面的元素的稳定性打乱，比如序列为 5 3 3 4 3 8 9 10 11， 现在中枢元素5和3(第5个元素，下标从1开始计)交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a[j]交换的时刻。
#include <stdio.h>
#include <stdlib.h>
int partiton(int array[], int low, int high) {
//基准数据
int key = array[low];
while (low < high) {
//因为默认基准是从左边开始，所以从右边开始比较
//当队尾的元素大于等于 基准数据 时,就一直向前挪动high指针
while (low < high && array[high] >= key) {
high--;
}
//当找到比 array[low] 小的时，就把后面的值 array[high] 赋给它
if (low < high) {
array[low] = array[high];
}
//当队首元素小于等于 基准数据 时,就一直向后挪动low指针
while (low < high && array[low] <= key) {
low++;
}
//当找到比 array[high] 大的时，就把前面的值 array[low] 赋给它
if (low < high) {
array[high] = array[low];
}
}
//跳出循环时low和high相等,此时的low或high就是key的正确索引位置
//把基准数据赋给正确位置
array[low] = key;
return low;
}
void quickSort(int array[], int low, int high) {
//开始默认基准为 low=0
if (low < high) {
//分段位置下标
int standard = partiton(array, low, high);
//递归调用排序
//左边排序
quickSort(array, low, standard - 1);
//右边排序
quickSort(array, standard + 1, high);
}
}
void display(int array[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", array[i]);
}
printf("\n");
}
bool check(int array[], int size) {
bool res = true;
for (int i = 0; i < size - 1; i++) {
if (array[i] > array[i + 1]) {
res = false;
}
}
return res;
}
int main() {
// int array[] = { 49,38,65,97,76,13,27,49,10 };
// int size = sizeof(array) / sizeof(int);
// printf("%d \n", size);
// quickSort(array, 0, size - 1);
int size = 25; //数组大小
int array[25] = { 0 }; //数组初始化
for (int i = 0; i < 100; i++) { //100个数组测试
for (int j = 0; j < size; j++) {
array[j] = rand() % 1000; //随机生成数组 0~999
}
printf("原来的数组：");
display(array, size);
quickSort(array, 0, size - 1);
printf("排序后数组：");
display(array, size);
if (check(array, size) == true) {
printf("排序成功\n");
}
printf("\n");
}
return 0;
}
归并排序是把序列递归地分成短序列，递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列，不断合并直到原序列全部排好序。可以发现，在1个或2个元素时，1个元素不会交换，2个元素如果大小相等也没有人故意交换，这不会破坏稳定性。那么，在短的有序序列合并的过程中，稳定是是否受到破坏？没有，合并过程中我们可以保证如果两个当前元素相等时，我们把处在前面的序列的元素保存在结果序列的前面，这样就保证了稳定性。所以，归并排序也是稳定的排序算法。
java实现代码：
public static void mergeSort(int[] arr) {
sort(arr, 0, arr.length - 1);
}
public static void sort(int[] arr, int L, int R) {
if(L == R) {
return;
}
int mid = L + ((R - L) >> 1);
sort(arr, L, mid);
sort(arr, mid + 1, R);
merge(arr, L, mid, R);
}
public static void merge(int[] arr, int L, int mid, int R) {
int[] temp = new int[R - L + 1];
int i = 0;
int p1 = L;
int p2 = mid + 1;
// 比较左右两部分的元素，哪个小，把那个元素填入temp中
while(p1 <= mid && p2 <= R) {
temp[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
// 上面的循环退出后，把剩余的元素依次填入到temp中
// 以下两个while只有一个会执行
while(p1 <= mid) {
temp[i++] = arr[p1++];
}
while(p2 <= R) {
temp[i++] = arr[p2++];
}
// 把最终的排序的结果复制给原数组
for(i = 0; i < temp.length; i++) {
arr[L + i] = temp[i];
}
}
https://www.jianshu.com/p/33cffa1ce613
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以其是稳定的排序算法。
希尔排序是按照不同步长对元素进行插入排序，当刚开始元素很无序的时候，步长最大，所以插入排序的元素个数很少，速度很快；当元素基本有序了，步长很小，插入排序对于有序的序列效率很高。所以，希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以shell排序是不稳定的。
我们简单处理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1} n为要排序数的个数
即：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。
void print(int a[], int n ,int i){
cout<<i <<":";
for(int j= 0; j<8; j++){
cout<<a[j] <<" ";
}
cout<<endl;
}
/**
* 直接插入排序的一般形式
*
* @param int dk 缩小增量，如果是直接插入排序，dk=1
*
*/
void ShellInsertSort(int a[], int n, int dk)
{
for(int i= dk; i<n; ++i){
if(a[i] < a[i-dk]){ //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入
int j = i-dk;
int x = a[i]; //复制为哨兵，即存储待排序元素
a[i] = a[i-dk]; //首先后移一个元素
while(x < a[j]){ //查找在有序表的插入位置
a[j+dk] = a[j];
j -= dk; //元素后移
}
a[j+dk] = x; //插入到正确位置
}
print(a, n,i );
}
}
/**
* 先按增量d（n/2,n为要排序数的个数进行希尔排序
*
*/
void shellSort(int a[], int n){
int dk = n/2;
while( dk >= 1 ){
ShellInsertSort(a, n, dk);
dk = dk/2;
}
}
int main(){
int a[8] = {3,1,5,7,2,4,9,6};
//ShellInsertSort(a,8,1); //直接插入排序
shellSort(a,8); //希尔插入排序
print(a,8,8);
}
我们知道堆的结构是节点i的孩子为2i和2i+1节点，大顶堆要求父节点大于等于其2个子节点，小顶堆要求父节点小于等于其2个子节点。在一个长为n的序列，堆排序的过程是从第n/2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n/2-1, n/2-2, ...1这些个父节点选择元素时，就会破坏稳定性。有可能第n/2个父节点交换把后面一个元素交换过去了，而第n/2-1个父节点把后面一个相同的元素没有交换，那么这2个相同的元素之间的稳定性就被破坏了。所以，堆排序不是稳定的排序算法
堆实际上是一棵完全二叉树，其任何一非叶节点满足性质： Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]（小顶堆）或者：Key[i]>=Key[2i+1]&&key>=key[2i+2]（大顶堆） 即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。
利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。
将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；
将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];
由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
#include <iostream>
using namespace std;
int arrs[] = { 23, 65, 12, 3, 8, 76, 345, 90, 21, 75, 34, 61 };
int arrLen = sizeof(arrs) / sizeof(arrs[0]);
void adjustHeap(int * arrs, int p, int len){
int curParent = arrs[p];
int child = 2* p + 1; //左孩子
while(child < len){ //没有孩子
if(child+1<len&&arrs[child]<arrs[child+1]){
child++; //较大孩子的下标
}
if(curParent<arrs[child]){
arrs[p]=arrs[child];
//没有将curParent赋值给孩子是因为还要迭代子树，
//如果其孩子中有大的，会上移，curParent还要继续下移。
p=child;
child=2*p+1;
}
else
break;
}
arrs[p]=curParent;
}
void heapSort(int * arrs, int arrLen){
//建立堆，从最底层的父节点开始
for(int i = arrLen /2 -1; i>=0; i--)
adjustHeap(arrs, i, arrLen);
for(int i = arrLen -1; i>=0; i--){
int maxEle = arrs[0];
arrs[0] = arrs[i];
arrs[i] = maxEle;
adjustHeap(arrs, 0, i);
}
}
int main()
{
heapSort(arrs, arrLen );
for (int i = 0; i < arrLen; i++)
cout << arrs[i] << endl;
return 0;
}