基本概念
- 稳定性
如果i==j,且i在j前面,排序完成后i仍旧在j前面则这个排序算法是稳定的,否则不稳定。
插入类排序
- 直接插入排序
/**直接插入排序
时间复杂度:O(n^2)
空间复杂度:O(1)
*/
void InsertSort(int R[], int n){int i, j;int temp;for(i=1; i=0 && temp
-
直接选择排序
在所有元素中选择出最小的,将元素位置与第一个交换,再将剩余元素重复上述过程,直至有序。 -
折半插入排序
/**折半插入排序
时间复杂度:O(n^2)
空间复杂度:O(1)
*/
void BinaryInsertSort(int R[], int n){int low, high, m; int i, j, temp;for(i=1; i temp)high = m-1;elselow = m+1;}for(j=i-1; j>high; --j) //将high后面的元素全部后移一位 R[j+1] = R[j];R[high+1] = temp; //插入元素 }
}
- 希尔排序
/**希尔排序
时间复杂度:O(n^2)
空间复杂度:O(1)
*/
void ShellSort(int R[], int n){int i, j, temp, k; int gap; //gap为步长 for(gap=n/2; gap>0; gap/= 2){ //将步长每次缩短一半 //对gap个子序列全部进行排序 for(i=0; i=0 && R[k]>temp){R[k+gap] = R[k];k -= gap;}R[k+gap] = temp;}}}}
}
交换类排序
- 冒泡排序
/**冒泡排序
时间复杂度:O(n^2)
空间复杂度:O(1)
*/
void BubbleSort(int R[], int n){int i, j, flag, temp;for(i=n-1; i>=1; --i){ //使下标为 i 的元素始终为最大值 flag = 0; //标记变量 该趟是否发生了改变 for(j=1; j<=i; ++j){ if(R[j-1] > R[j]){ //交换元素 temp = R[j];R[j] = R[j-1];R[j-1] = temp;flag = 1; //flag==1 证明该趟发生了交换 }}if(flag == 0) //如果未发生交换代表序列有序 return;}
}
- 快速排序
/**快速排序
时间复杂度:O(n*log2^n)
空间复杂度:O(log2^n)
*/
void QuickSort(int R[], int low, int high){int temp;int i=low, j=high;if(low < high){ temp = R[low]; //保存枢纽元素 //循环将元素分为 {小于枢纽 枢纽 大于枢纽} while(ii && R[j]>=temp) --j; //从左往右扫描找到小于temp的元素 if(i
- 堆排序
先建堆,取堆顶,再重复。堆为一个完全二叉树。
算法比较
| 排序算法 | 时间复杂度 | 空间复杂度 | 算法稳定性 |
|---|---|---|---|
| 直接插入排序 | O(n^2) 最坏、平均 O(n) 最好 | O(1) | 稳定 |
| 折半插入排序 | O(n^2) 最坏、平均 O(n*log2^n) 最好 | O(1) | 稳定 |
| 希尔排序 | O(n^2) | O(1) | 不稳定 |
| 冒泡排序 | O(n^2) 最坏、平均 O(n) 最好 | O(1) | 稳定 |
| 快速排序 | O(n^2) 最坏 O(n*log2^n)最好、平均 | O(log2^n) | 不稳定 |
| 简单选择排序 | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(n*log2^n) | O(1) | 不稳定 |
| 二路归并排序 | O(n*log2^n) | O(n) | 稳定 |
| 基数排序 | O(d(n+r_d)) 最坏、平均 n:序列关键字数 d:关键字的关键位数 r_d:关键字基的个数 | O(r_d) | 稳定 |
稳定性:快速排序、希尔排序、简单选择排序、堆排序 是不稳定的,其余都是稳定的。










