C 语言常见排序算法实现与解析 | 极客日志

C算法

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

C 语言中八种常见排序算法的实现细节与分析。涵盖冒泡、选择、插入、堆排序、希尔排序、快速排序、归并排序及计数排序。内容包括各算法的逻辑原理、C 语言代码实现、时间复杂度评估及稳定性判定。特别针对快速排序提供了霍尔法、挖洞法、快慢指针法三种实现及非递归栈优化方案，并讨论了归并排序的递归与非递归写法。旨在帮助读者深入理解排序算法的核心机制与应用场景。

数字游民发布于 2026/3/30更新于 2026/4/132 浏览

前言

以下算法均以升序为例。排序算法的稳定性评估：相同的值在排序后相对位置是否改变。辅助函数：交换与打印数组。

 {
     i = ;
    (i = ; i < n; i++){
        (, a[i]);
    }
    ();
}

 {
     tmp = *a1;
    *a1 = *a2;
    *a2 = tmp;
}

void BubbleSort(int* a, int n){
    int i = 0;
    int j = 0;
    int flag = 0;
    for(i = 0; i < n - 1; i++) {
        flag = 0;
        for(j = 0; j < n - 1 - i; j++){
            if(a[j] > a[j + 1]){
                Swap(&a[j], &a[j + 1]);
                flag = 1;
            }
        }
        if(!flag) break;
    }
}

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;
    }
}

// 把第 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;
    }
}

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);
    }
}

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;
        }
    }
}

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;
}

// 霍尔法
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;
}

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);
}

// 用顺序表实现栈
#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;
}

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);
}

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;
}

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;
}

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);
}

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

前言

一、冒泡排序

1. 实现逻辑

2. 代码实现

3. 代码分析

二、选择排序

1. 实现逻辑

2. 实现代码

3. 代码分析

三、插入排序

1. 实现逻辑

2. 实现代码

3. 代码分析

四、堆排

1. 实现逻辑

2. 代码实现

3. 代码分析

五、希尔排序

1. 实现逻辑

2. 代码实现

3. 代码分析

六、快排

1. 实现逻辑

2. 代码实现

3. 代码分析

七、归并排序

1. 基本逻辑

2. 代码实现

3. 代码分析

八、计数排序

1. 实现逻辑

2. 代码实现

3. 代码分析

更多推荐文章

相关免费在线工具

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

前言

一、冒泡排序

1. 实现逻辑

2. 代码实现

3. 代码分析

二、选择排序

1. 实现逻辑

2. 实现代码

3. 代码分析

三、插入排序

1. 实现逻辑

2. 实现代码

3. 代码分析

四、堆排

1. 实现逻辑

2. 代码实现

3. 代码分析

五、希尔排序

1. 实现逻辑

2. 代码实现

3. 代码分析

六、快排

1. 实现逻辑

2. 代码实现

3. 代码分析

七、归并排序

1. 基本逻辑

2. 代码实现

3. 代码分析

八、计数排序

1. 实现逻辑

2. 代码实现

3. 代码分析

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具