十大排序算法总结
基础交换函数
void swap(int& temp1, int& temp2)
{
temp1 = temp1 ^ temp2;
temp2 = temp1 ^ temp2;
temp1 = temp1 ^ temp2;
}
冒泡排序
算法流程
- 比较相邻元素，如果满足条件则交换（视从小到大排，和从大到小排定）
- 顺序比较，直到最后一位，则最后一位已排好序
- 重复以上步骤，但已经排好的不参与比较。
复杂度分析
- 时间复杂度（平均）： O(n^2)
- 时间复杂度（最好）： O(n) 初始已排序（改进算法才可以）
- 时间复杂度（最坏）： O(n^2)
- 是否稳定： 稳定
C代码
冒泡排序
void bubbleSort(int array[], int length)
{
for (int i = 0; i<length-1; i++) // 这一步控制步长
{
for (int j = 0; j < length -1 -i;j++) // 这一步前后排序
{
if (array[j] > array[j+1])
{
swap(array[j], array[i]);
}
}
}
}
选择排序
算法流程
- 遍历比较确定数组中最小值所在的下标
- 最小值与第一位未排序好的数交换
- 重复以上步骤，但已经排好的不参与比较。
复杂度分析
- 时间复杂度（平均）： O(n^2)
- 时间复杂度（最好）： O(n) 初始已排序（改进算法才可以）
- 时间复杂度（最坏）： O(n^2)
- 是否稳定： 稳定
C代码
选择排序
void selectSort(int array[], int length) {
int minIndex;
for (int i = 0; i < length - 1; i++) {
minIndex = i;
for (int j = i + 1; j < length; j++) {
if ( array[j] < array[minIndex] ) { // 寻找最小的数
minIndex = j; // 将最小数的索引保存
}
}
swap(array[i], array[minIndex]);
}
}
插入排序
算法流程
- 类似斗地主叠排
- 默认第一个已经排好，待插入的值与前面的比较，若小于，则前后的后移
- 直到待插入的值大于前一个值
- 未排序的数重复以上步骤。
复杂度分析
- 时间复杂度（平均）： O(n^2)
- 时间复杂度（最好）： O(n)
- 时间复杂度（最坏）： O(n^2)
- 是否稳定： 稳定
C代码
插入排序
void insertSort(int array[], int length)
{
int preIndex, current;
for (int i = 1; i < length; i++) {
preIndex = i - 1;
current = array[i];
while (preIndex >= 0 && array[preIndex] > current) {
array[preIndex + 1] = array[preIndex];
preIndex--;
}
array[preIndex + 1] = current;
}
}
希尔排序
算法流程
- 确定间隔数组，这里采用3的倍数递增法，可换，最后一个间隔需为1
- 按照不同的间隔进行直接插入排序
复杂度分析
- 时间复杂度（平均）： O(n^1.3) 统计结果
- 时间复杂度（最好）： O(n)
- 时间复杂度（最坏）： O(n^2)
- 是否稳定： 不稳定 间隔排序导致
C代码
希尔排序
void shellSort(int array[], int length)
{
int gap = 1, current;
int i, preIndex;
while (gap < length / 3) { // 动态定义间隔序列
gap = gap * 3 + 1; // 保证除3的时候会取到1
}
for ( ; gap > 0; gap = floor(gap / 3 ) ) {
// 间隔为gap的直接插入排序,这里除了前几个数外，都需要与之前的比较
for (i = gap; i < length; i++) {
current = array[i];
preIndex = i - gap;
// 注意取值范围
while (preIndex >= 0 && array[preIndex] > current) {
array[preIndex + gap] = array[preIndex];
preIndex = preIndex - gap;
}
array[preIndex + gap] = current;
}
}
}
归并排序
算法流程
- 参考算法导论的分而治之的思想
- 递归将大的数组分为左右两部分，一直分到只剩最后一个值
- 逆递归merge排序，开辟新空间将两个数组最小值比较，排序到原数组空间中
- 技巧是设置无穷大的哨兵值，毕竟不断的判断是否数组已经遍历到结尾
复杂度分析
- 时间复杂度（平均）： O(nlog(n))
- 时间复杂度（最好）： O(nlog(n))
- 时间复杂度（最坏）： O(nlog(n))
- 是否稳定： 稳定
C代码
合并函数
void merge(int array[], int begin, int middle, int end) {
int len1 = middle - begin + 1;
int len2 = end - middle;
int i, j;
// 定义中间变量
int *arr1 = new int[len1 + 1];
int *arr2 = new int[len2 + 1];
// 赋初值
for (i = 0; i < len1; i++)
{
*(arr1 + i) = array[begin + i];
}
for (j = 0; j < len2; j++)
{
*(arr2 + j) = array[middle + j + 1];
}
// 设置哨兵
arr1[len1] = 10000;
arr2[len2] = 10000;
// 从最前面遍历
i = 0;
j = 0;
for (int k = begin; k <= end; k++)
{
if (arr1[i] < arr2[j])
{
array[k] = arr1[i];
i++;
}
else
{
array[k] = arr2[j];
j++;
}
}
delete arr1;
delete arr2;
}
归并排序
void mergeSort(int array[], int begin, int end)
{
int middle = floor((end + begin) / 2);
// 先分后和
if (begin < end) {
mergeSort(array, begin, middle);
mergeSort(array, middle + 1, end);
merge(array, begin, middle, end);
}
}
快速排序
算法流程
- 选择第一个为基数，将余下的数按照是否大于或者小于，归于两边
- 为了使用原空间，采用左右震荡比较方式比较
- 最小值与第一位未排序好的数交换
- 分左右递归以上步骤。
复杂度分析
- 时间复杂度（平均）： O(nlog(n))
- 时间复杂度（最好）： O(n^2) 初始无序
- 时间复杂度（最坏）： O(nlog(n))
- 是否稳定： 不稳定 左右震荡导致
C代码
快速排序
void quickSort(int array[], int left, int right)
{
if (left < right) {
int temp = array[left];
int indexL = left;
int indexR = right;
while (indexR > indexL)
{
// 只要有涉及下标运算，都需要判断
// 右振荡
while (indexR > indexL && array[indexR] >= temp)
{
indexR--;
}
if(indexR > indexL)
array[indexL++] = array[indexR];
// 左振荡
while (indexR > indexL && array[indexL] < temp)
{
indexL++;
}
if (indexR > indexL)
array[indexR--] = array[indexL];
}
// 计算完后 indexR = indexL = 最中间的下标
array[indexR] = temp;
// 递归
quickSort(array, left, indexR - 1);
quickSort(array, indexR + 1, right);
}
}
堆排序
算法流程
- 主要过程分为调整堆，将为排好序的最大值交换到已排好序的最后
- 重复以上步骤，但已经排好的不参与比较。
- 这里一个技巧就是利用 二叉堆，根节点与子节点的关系。
复杂度分析
- 时间复杂度（平均）： O(nlog(n))
- 时间复杂度（最好）： O(nlog(n))
- 时间复杂度（最坏）： O(nlog(n))
- 是否稳定： 不稳定 调整导致
C代码
堆排序
void adjustHeap(int array[], int len)
{
int maxIndex, rootIndex, subLeftIndex, subRightIndex;
// 从下往上调整
for (int i = len / 2; i > 0; i--){
// C的下标从0开始
rootIndex = i - 1;
maxIndex = rootIndex;
subLeftIndex = 2 * i -1;
subRightIndex = 2 * i;
if (array[maxIndex] < array[subLeftIndex])
maxIndex = subLeftIndex;
// 右子节点需要判断是否越界
if ( subRightIndex< len && array[maxIndex] < array[subRightIndex])
maxIndex = subRightIndex;
// 根节点与最大节点交换
if( maxIndex != rootIndex)
swap(array[rootIndex], array[maxIndex]);
}
}
void heapSort(int array[], int len)
{
int adjustLen = len;
for (int i = 0; i < len - 1 ; i++) {
adjustHeap(array, adjustLen);
// C的下标从0开始的
swap(array[0], array[adjustLen-1]);
adjustLen--;
}
}
计数排序
算法流程
- 条件限制： 待排序数组一定是一定范围内的整数
- 首先取得最大最小值，确定辅助数组大小k。
- 遍历待排序数组，与值对应，辅助数组相应位置+1。遍历后辅助数组相应下标存放值的数目
- 遍历将值按顺序存回原数组，则排序完成
复杂度分析
- 时间复杂度（平均）： O(n+k)
- 时间复杂度（最好）： O(n+k) 初始已排序（改进算法才可以）
- 时间复杂度（最坏）： O(n+k)
- 是否稳定： 稳定
C代码
计数排序
void countSort(int array[], int len)
{
int minValue = array[0];
int maxValue = array[0];
// 获得最小最大值，确定排序边界
for (int i = 1; i < len; i++) {
if (array[i] < minValue)
minValue = array[i];
if (array[i] > maxValue)
maxValue = array[i];
}
int countLen = maxValue - minValue + 1;
int * countArray = new int[countLen];
// 清0
for (int i = 0; i < countLen; i++) {
countArray[i] = 0;
}
// 计算数目
for (int i = 0; i < len; i++) {
countArray[array[i] - minValue] ++;
}
// 计算数目
int j = 0;
for (int i = 0; i < countLen; i++) {
while ( countArray[i] != 0 )
{
array[j++] = i + minValue;
countArray[i]--;
}
}
delete countArray;
}
桶排序
算法流程
- 基于分组排序思想
- 设置一个定量的数组当作空桶
- 遍历输入数据，并且把数据一个一个放到对应的桶里去
- 对每个不是空的桶进行排序；
- 把排好序的数据拼接起来
复杂度分析
- 时间复杂度（平均）： O(n+k)
- 时间复杂度（最好）： O(n)
- 时间复杂度（最坏）： O(n^2)
- 是否稳定： 稳定
C代码
基数排序
算法流程
- 取得数组中的最大数，并取得位数
- 从最低位开始取每个位组成 待排数组；
- 待排数组进行计数排序
复杂度分析
- 时间复杂度（平均）： O(n*k)
- 时间复杂度（最好）： O(n*k)
- 时间复杂度（最坏）： O(n*k)
- 是否稳定： 稳定
网友评论