C 语言常见排序算法实现与解析

3. 代码分析

时间复杂度：O(N^2)。 稳定性：稳定，因为遇到相等的值不会交换位置。

二、选择排序

1. 实现逻辑

每次遍历一边数组，把最小最大的值选出，然后分别置于 start 位置和 end 位置。 start：开始是要排的数组的开头，每选一个最小值 +1； end：开始是要排的数组的末尾，每选一个最小值 -1；

2. 实现代码

void SelectSort(int* a, int n){
    int i = 0;
    int j = 0;
    int start = 0;
    int end = n - 1;
    int min = 0;
    int max = 0;
    while(start < end){
        min = start;
        max = start;
        for(i = start; i <= end; i++){
            if(a[i] > a[max]) max = i;
            if(a[i] < a[min]) min = i;
        }
        /* if (max != start) { Swap(&a[start], &a[min]); Swap(&a[end], &a[max]); } else { Swap(&a[end], &a[max]); Swap(&a[start], &a[min]); }*/
        if(max == start) max = min;
        Swap(&a[start], &a[min]);
        Swap(&a[end], &a[max]);
        ++start;
        --end;
    }
}

注意 max 是开头元素的情况！

3. 代码分析

时间复杂度：约看作要走 n 遍数组：O(N^2)。 稳定性：不稳定，找到最值并放置最值后相同值的相对顺序可能会变。

三、插入排序

1. 实现逻辑

就像打扑克牌时我们习惯性的给手牌排序一样，先确定一个区间 (开始元素个数为 1)，取该区间末尾后一位数 (temp) 与区间末尾的值进行比较： temp < x：将 x 的值向后一位，end–, 在重复比较； temp >= x: 将 temp 放在 x 的后面；

2. 实现代码

// 把第 end+1 位置的值插入 [0,end] 里并保持有序
void InsertSort(int* a, int n){
    int i = 0;
    int end = 0;//[0,end] 为有序区间的范围
    for(i = 0; i < n - 1; i++){
        end = i;
        int tmp = a[end + 1];//保存要移动的值
        while(end >= 0){
            if(tmp < a[end]){ 
                a[end + 1] = a[end];
                --end;
            }else{
                break;//存在 tmp<有序区间内所有值以及找到比它小的值两种情况
            }
        } 
        a[end + 1] = tmp;
    }
}

注意要插入的值为最小的情况！

3. 代码分析

时间复杂度：最快情况与冒泡相似，故O(N^2)，但它比以上两种 O(N) 算法快。 稳定性：稳定，插入不会改变相同值的相对顺序。

四、堆排

1. 实现逻辑

建堆，然后以删除堆顶元素的思想，不断将最大值往最后面放。

2. 代码实现

void AdjustDown(int* a, int parent, int n){
    int child = parent * 2 + 1;
    int i = 0;
    while(child < n){
        if(child + 1 < n && a[child] < a[child + 1]){ 
            child++;
        }
        if(a[parent] < a[child]){
            Swap(&a[parent], &a[child]);
            parent = child;
            child = parent * 2 + 1;
        }else return;
    }
}

void HeapSort(int* a, int n){
    int i = 0;
    for(i = (n - 1)/2; i >= 0; i--){
        AdjustDown(a, i, n);
    }
    i = n;
    while(i > 0){
        Swap(&a[i - 1], &a[0]);
        i--;
        AdjustDown(a, 0, i);
    }
}

3. 代码分析

时间复杂度：最坏情况就是每次都得将堆顶元素移至最后一层：O(NlogN),以 2 为底。 稳定性：不稳定，试想堆里面有大量相同的值。

五、希尔排序

1. 实现逻辑

取一值 gap，将数组分成 gap 组 (想象)： 第一组：从下标为 0 开始，每个 gap 个空：0，0+gap，0+gap+gap…为一组； 第二组：从下标为 1 开始，每个 gap 个空：1，1+gap，1+gap+gap…为一组； …… 第 gap 组：下标为 gap-1 开始，每个 gap 个空：gap-1，gap-1+gap…为一组； 然后对每组使用插入排序的思想对每组排序。 以上称为预排序，它会降低插入排序的负担。预排结束后再对整个数组进行插入排序即可。 但是，gap 太小预排的消耗就接近与插入排序了；gap 太大又让后面的插入排序负担变重。两种情况都会让该排序近似于插入排序，可是对于大小不同的数组，最合适的 gap 是不同的，也不好找。因此我们可以让 gap 持续变化。

2. 代码实现

void ShellSort(int* a, int n){
    int i = 0;
    int end = 0;
    int gap = n;
    //int gap = 3;
    //int j = 0;
    //for (j = 0; j < gap; j++)
    //{
    // for (i = j; i < n - gap; i += gap)
    // {//
    //  end = i;
    //  int tmp = a[end + gap];
    //  while (end >= 0)
    //  {//
    //   if (tmp < a[end])
    //   {//
    //    a[end + gap] = a[end];
    //    end -= gap;
    //   }
    //   else
    //   break;
    //  }
    //  a[end + gap] = tmp;
    // }//
    //}//
    //for (i = 0; i < n - gap; i++)
    //{//
    // end = i;
    // int tmp = a[end + gap];
    // while (end >= 0)
    // {//
    //  if (tmp < a[end])
    //  {//
    //   a[end + gap] = a[end];
    //   end -= gap;
    //  }
    //  else
    //  break;
    // }//
    // a[end + gap] = tmp;
    //}//
    //简化：while(gap >1){ gap = gap /3+1;//gap 太大太小都不好，直接不停改变它;//+1 是为了让 gap 最后一定为 1//研究表明，这个值比较适合//gap 为 1 时就直接是插入排序了
    while(gap > 1){
        gap = gap / 3 + 1;
        for(i = 0; i < n - gap; i++){
            end = i;
            int tmp = a[end + gap];
            while(end >= 0){
                if(tmp < a[end]){ 
                    a[end + gap] = a[end]; 
                    end -= gap;
                }else break;
            } 
            a[end + gap] = tmp;
        }
    }
}

一定要让 gap 最后为 1！！

3. 代码分析

时间复杂度：O(N^1.3); 稳定性：不稳定，相同值会处于不同组，相对位置不可控。

六、快排

1. 实现逻辑

可以先看其中一个逻辑再看其他的。

a. 霍尔法 取数组的某一下标为 keyi，通常取末尾或开头，这里取开头。然后定义 left 与 right 两个下标，分别从开头和末尾走，left 找比下标为 keyi 的值大的元素，right 找小的，让 left 找到的大的与 right 找到的小的交换位置，直到 left=right，将 keyi 对应的值放在它们相遇的位置。这样就把 keyi 的值固，其左边为比其小的数，右边为比其大的数。然后以 keyi 为分界点，将数组分成两份，继续该操作。

b. 挖洞法 与霍尔法类似，依旧是 left 找大的，right 找小的，不同的是，我们先存下 keyi 对应的值，走 right，找到小的后自接赋值给 left 所在位置，然后 left 走，找到大的赋值给 right 所在位置；如此往复，直至相遇；最后把 keyi 对应的值赋值给相遇的位置。

c. 快慢指针法 定义 prev(为数组第一个元素下标)，cur(数组第二个元素下标)。然后让 cur 先走，如果所到下标的值小于 keyi 对应的值，则 prev 走一步在将 cur 对应的值赋给 prev；如果大于大于 keyi 对应的值，则 prev 不动，cur 继续走，如果遇到小的就重复第一种情况，找到 cur 走出数组。最后交换 keyi 与 prev 对应的值，并将 prev 赋给 keyi。

2. 代码实现

单用上面的逻辑实现快排其实是比较鸡肋的，有些情况它的运行时间接近于 O(N^2)，因此我们要对其进一步优化。

a. 试想，如果要排序的数组是已经排好序或接近排好序的，你每次取开头做 keyi 的话要这样不断的分 n 次，left 于 right 每一次都得走 n 步 (两者要相遇)，这样的话时间复杂度上升到 O(N^2) 了。但是我们又不能改变算法的基本逻辑，我们该怎么办呢？ 我们可以取下标为 left，right，(left + right)/2 的数据进行比较选出中间的那个数，然后把它放在 left 位置，这样我们可以把每次分割都看成对半分 (实际不是，粗略估算)，这样时间复杂度就来到 O(NlogN) 了。

int GetMid(int* a, int left, int right){
    int midi = 0;
    int mid = (right + left)/2;
    if(a[mid] > a[left]){
        if(a[mid] < a[right]) midi = mid;
        else{
            if(a[right] > a[left]) midi = right;
            else midi = left;
        }
    }else{
        if(a[mid] > a[right]) midi = mid;
        else{
            if(a[left] > a[right]) midi = right;
            else midi = left;
        }
    }
    return midi;
}

b. 对于递归实现该算法： 基于 a，我们可以得到如果用递归实现，那么绝大多数的栈帧开辟会集中在最后 (将数组分成一两个数一组的情况)，那么为了解决这个问题，我们可以在分割的数组内数据个数在几个（如 10 个）时，用简单的算法直接对它们排序 (推荐插入排序)，直接就极大提升了效率。

三种思路：

// 霍尔法
int QuickSort_Part1(int* a, int left, int right){
    int keyi = left;//关键下标取左边的，但如果数组为顺序这个算法将非常吃力，因此我们要对 a[keyi] 进行调整
    int begin = left;
    int end = right;
    while(end > begin)//这里排升序，将大于 a[keyi] 的值全放在其右边，小于它的值放在左边
    {
        while(end > begin && a[end]>= a[keyi])//右边开始走，找到小于 a[keyi] 的下标为止
        {
            --end;
        }
        while(end > begin && a[begin]<= a[keyi])//左边开始走，找到大于 a[keyi] 的下标为止
        {
            ++begin;
        }
        Swap(&a[end], &a[begin]);
    }
    Swap(&a[keyi], &a[begin]);//这里 left 与 right 在相同位置，且该位置的值必小于 a[keyi] keyi = begin;
    return keyi;
}

// 挖洞法快排
int QuickSort_Part2(int* a, int left, int right){
    int keyi = left;//刚开始洞的位置
    int begin = left;
    int end = right;
    while(end > begin){
        while(end > begin && a[end]>= a[keyi]){
            --end;
        } 
        a[begin]= a[end];
        while(end > begin && a[begin]<= a[keyi]){
            ++begin;
        } 
        a[end]= a[begin];
    } 
    a[begin]= a[keyi]; 
    keyi = begin;
    return keyi;
}

// 快慢指针法
int QuickSort_Part3(int* a, int left, int right){
    int keyi = left;
    int prev = left;
    int cur = prev + 1;//排升序就是找比 keyi 小的
    while(cur <= right){
        if(a[cur]< a[keyi]&&++prev != cur)Swap(&a[cur], &a[prev]); 
        cur++;
    }
    Swap(&a[keyi], &a[prev]); 
    keyi = prev;
    return keyi;
}

1. 递归实现

void QuickSort(int* a, int left, int right){
    if(left >= right) return;
    if(right - left + 1 >= 10)//要调整的区间范围
    {
        InsertSort(a + left, right - left + 1);//可以大幅度减少开辟栈帧的次数
        return;
    }
    int midi = GetMid(a, left, right);
    Swap(&a[midi], &a[left]);//先将关键节点的值调整
    int keyi = QuickSort_Part1(a, left, right);//int keyi = QuickSort_Part2(a, left, right);//int keyi = QuickSort_Part3(a, left, right);
    QuickSort(a, left, keyi - 1);
    QuickSort(a, keyi + 1, right);
}

2. 非递归实现 观察递归函数我们可以发现，实现该算法最重要的就是要有 left 与 right，因此我们要想办法储存区间。我们可以用栈结构辅助完成： 栈的实现：

// 用顺序表实现栈
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
#include<time.h>
#include<string.h>

typedef int STDataType;
typedef struct Stack{
    STDataType* a;//栈
    int top;//可以选择指向栈顶元素，也可以选择记录栈的元素数据
    int capacity;//记录栈的容量
}ST;

// 栈的初始化
void Stack_Init(ST* pst);
// 栈的销毁
void Stack_Destroy(ST* pst);
// 入栈
void Stack_Push(ST* pst, STDataType x);
// 出栈
void Stack_Pop(ST* pst);
// 取栈顶元素
STDataType Stack_Top(ST* st);
// 取栈元素个数
int Stack_Size(ST* st);
// 判空
bool IsEmpty(ST* pst);

#include"Sort.h"

// 栈的初始化
void Stack_Init(ST* pst){
    assert(pst); 
    pst->a = NULL; 
    pst->capacity = pst->top = 0;
    // 这里将 top 初始化为 0 就表示 top 指的是栈中元素的个数，指向栈顶的下一位
    // 如果要让 top 指向栈顶元素处，要将 top 初始化为 -1
}

// 栈的销毁
void Stack_Destroy(ST* pst){
    assert(pst);
    free(pst->a); 
    pst->a = NULL; 
    pst->capacity = pst->top = 0;
}

// 入栈
void Stack_Push(ST* pst, STDataType x){
    assert(pst);
    if(pst->top == pst->capacity){
        int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
        // 让栈的空间初始可以容纳四个元素，之后空间成倍增加
        STDataType* tobig = (STDataType*)realloc(pst->a, sizeof(STDataType)* newcapacity);
        if(!tobig){
            perror("StackPush:error realloc");
            return;
        } 
        pst->a = tobig; 
        pst->capacity = newcapacity;
    } 
    pst->a[pst->top]= x; 
    pst->top++;//每入栈一次，空间加一
}

// 出栈
void Stack_Pop(ST* pst){
    assert(pst);
    assert(pst->top);//有元素才能出
    (pst->top)--;//让元素个数减一即可
}

// 取栈顶元素
STDataType Stack_Top(ST* pst){
    assert(pst);
    assert(pst->top);//有元素才能取
    return pst->a[pst->top - 1];
}

// 计算栈元素个数
int Stack_Size(ST* pst){
    assert(pst);
    return pst->top;
}

// 判空
bool IsEmpty(ST* pst){
    assert(pst);
    return pst->top == 0;
}

我们要先把初始的 left 与 right 压入栈中，要确定区间时就将它们弹出；如何分割区间时就把新区间的左右边界一次压入栈中。因为栈有先进后出的特性，因此我们一定要注意压栈顺序。

void QuickSort_NonR(int* a, int left, int right)//非递归形式的快排；要引入栈或队列
// 将要排的数据的区间开始与结束的值 Push 入栈，每次要排时就弹出，直到 stack 为空就结束
{
    ST st;
    Stack_Init(&st);
    // 先进后出，先放右
    Stack_Push(&st, right);
    Stack_Push(&st, left);
    int begin = left;
    int end = right;
    while(!IsEmpty(&st))//栈空了就结束
    {
        begin = Stack_Top(&st);
        Stack_Pop(&st);
        end = Stack_Top(&st);
        Stack_Pop(&st);
        if(end - begin + 1 <= 10){
            InsertSort(a + begin, end - begin + 1);
            continue;
        }
        int midi = GetMid(a, begin, end);
        Swap(&a[midi], &a[begin]);
        int keyi = QuickSort_Part1(a, begin, end);
        if(end > keyi + 1){
            Stack_Push(&st, end);
            Stack_Push(&st, keyi + 1);
        }
        if(begin < keyi - 1){
            Stack_Push(&st, keyi - 1);
            Stack_Push(&st, begin);
        }
    }
    Stack_Destroy(&st);
}

3. 代码分析

时间复杂度：经过优化，时间复杂度估算为O(NlogN). 稳定性：不稳定。可以试着排 1，2，3，4，5，5，5，5，9，3(随便选的)；注意相同数的下标。

七、归并排序

1. 基本逻辑

先开辟一个与原数组大小相等的数组，将需排序数组分割平均分成两份，然后如果两个数组都有序，那么开始遍历取 begin1 与 begin2 分别开始遍历两个数组，比较 begin1 与 begin2 对应的值，将更小的 (假设为 begin1) 放入新数组，则 begin1++，继续与 begin2 对应的值比较；如此反复，直到一个数组走到头，然后将还有剩的数组导入新数组。最后要把新数组的数据拷贝入原数组。 那么主要问题就是如何判断分割的数组有序？只有一个元素的数组不是有序嘛！！！

2. 代码实现

1. 递归实现

void _MergeSort(int* a, int* temp, int begin, int end){
    if(begin >= end) return;
    int mid = (begin + end)/2;
    // 先将左半边数据排成有序，再将右半边数据排成有序，最后将左右两组数据合并成有序
    // 按以上思想不断分割数组
    _MergeSort(a, temp, begin, mid);
    _MergeSort(a, temp, mid + 1, end);
    // [begin,mid][mid + 1,end]
    // 要将这两个区间内的数据按顺序赋给 temp，然后再从 temp 赋给原数组
    int begin1 = begin, end1 = mid;//第一个区间
    int begin2 = mid + 1, end2 = end;//第二个区间
    int i = begin;
    while(begin1 <= end1 && begin2 <= end2){
        if(a[begin1] < a[begin2]) temp[i++] = a[begin1++];
        else temp[i++] = a[begin2++];
    }
    while(begin1 <= end1) temp[i++] = a[begin1++];
    while(begin2 <= end2) temp[i++] = a[begin2++];
    memcpy(a + begin, temp + begin, sizeof(int)*(end - begin + 1));
}

void MergeSort(int* a, int n){
    int* temp = (int*)malloc(sizeof(int)* n);
    if(!temp){
        perror("MergeSort: error malloc");
        return;
    }
    _MergeSort(a, temp, 0, n - 1);
    free(temp); 
    temp = NULL;
}

2. 非递归实现 因为分数组时是二分，所以我们可以先规定一个元素为一个数组，将相邻的两个数组排序；然后个数2 变成每两个元素一个数组，将相邻的两个数组排序；然后2 变成 4 个元素一个数组……如此一来便能实现整体的排序。 过程：2 个元素有序、4、8……n 个。

void MergeSort_NonR(int* a, int n){
    int* temp = (int*)malloc(sizeof(int)* n);
    if(!temp){
        perror("MergeSort: error malloc");
        return;
    }
    int gap = 1;//每一次归并排序的两组中，每一组的元素个数
    int i = 0;
    while(gap < n){
        for(i = 0; i < n; i += 2 * gap){//要进行归并的两组数据的区间
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + gap + gap - 1;
            if(begin2 >= n)//说明第二组数据不存在
                break;//则这一对数据不用归并
            if(end2 >= n) end2 = n - 1;
            int j = i;
            while(begin1 <= end1 && begin2 <= end2){
                if(a[begin1] < a[begin2]) temp[j++] = a[begin1++];
                else temp[j++] = a[begin2++];
            }
            while(begin1 <= end1) temp[j++] = a[begin1++];
            while(begin2 <= end2) temp[j++] = a[begin2++];
            memcpy(a + i, temp + i, sizeof(int)*(end2 + 1 - i));//这里的 (end2 + 1 - i) 不能改成 2*gap，因为 end2 可能进入了前面的 if
        } 
        gap *= 2;
    }
    free(temp); 
    temp = NULL;
}

for 循环内的两个 if 很重要，因为数组中元素的个数不一定是 2 的次方数； 也要注意录入新数组是元素的下标。

3. 代码分析

时间复杂度：因为二分，所以会分成 logN 层，每层相邻数组都要归并，共走 n 步，故O(NlogN); 稳定性：稳定，归并不会改变相同数值的相对顺序。

八、计数排序

相比于前 7 个排序，计数排序的不同在于它不是靠比较数字大小的方法来排序的，而是开辟一个数组，为原数组中的每一个元素设置一个对应位置。

1. 实现逻辑

给出一组数据，找出 max 与 min，设 range = max-min+1，开辟一个可以存 range 个数据的空间 (要初始化为 0)；其中 min 对应新数组的中下标为 0 的位置，max 对应末尾下标，即 max-min；令数组中有一值为 x，则 x 对应新数组的下标为：x-min; 然后遍历原数组，每遍历到一个数，将该数在新数组中对应的位置的值 +1；遍历完后，遍历新数组，将新数组中的值当成个数 m，下标为 i，将 m 个 i+min 写入原数组中。

2. 代码实现

void CountSort(int* a, int n){
    int min = a[0];
    int max = a[0];
    int i = 0;
    int range = 0;
    int j = 0;
    for(i = 1; i < n; i++)//找到最值
    {
        if(a[i] > max) max = a[i];
        if(a[i] < min) min = a[i];
    } 
    range = max - min + 1;
    //printf("%d\n", range);
    int* count = (int*)calloc(range, sizeof(int));//因为要初始化为 0，所以用 calloc
    if(!count){
        perror("CountSort:error calloc");
        return;
    }
    for(i = 0; i < n; i++)//记下 a 中各数出现的次数
    { 
        count[a[i]- min]++;
    }
    for(i = 0; i < range; i++)//这个嵌套的时间复杂度为 O(N)
    {
        while(count[i]--){ 
            a[j++]= i + min;
        }
    }
    free(count);
}

3. 代码分析

时间复杂度：很显然为O(N); 稳定性：稳定； 缺陷：只能比较整数； 更加适合数值波动不大的数据。