算法基础：6种经典排序算法的递归和非递归实现

本文的算法实现主要参考两本书：
《算法导论》
《大话数据结构》

接口

#ifndef _SORT_H
#define _SORT_H

#define true 1
#define false 0

typedef int bool;

typedef int elem_t;

typedef struct{
    elem_t *a;
    int len;
} List;

void printlist(elem_t *a, int n, int sps);
bool listCompare(List *a1, List *a2,int n);
// ==============常用内部排序=================
// 冒泡排序（简单交换排序的改进）
extern void bubbleSort_RE(elem_t *a, int len);
extern void bubbleSort_NRE(elem_t *a, int len);
// 选择排序
extern void selectionSort_RE(elem_t *a, int n);
extern void selectionSort_NRE(elem_t *a, int n);
// 插入排序
extern void insertionSort_RE(elem_t *a, int n);
extern void insertionSort_NRE(elem_t *a, int n);
// 希尔排序（插入排序的改进）
extern void shellSort_RE(elem_t *a, int n);
extern void shellSort_NRE(elem_t *a, int n);
// 堆排序（简单选择排序的改进）
extern void heapSort_RE(elem_t *a, int n);
extern void heapSort_NRE(elem_t *a, int n);
// 归并排序
extern void mergeSort_RE(elem_t *a, int n);
extern void mergeSort_NRE(elem_t *a, int n);
// 快速排序（冒泡排序的改进）
extern void quickSort_RE(elem_t *a, int n);
extern void quickSort_NRE(elem_t *a, int n);

#endif

测试代码

注意

NRE表示非递归版本，RE表示递归版本
部分排序算法提供了两种版本的实现

// test_sort.c
#include "sort.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>


static const int n = 50;
static const int sps = 10;

int main(){
    List list;
    list.a = (elem_t *)malloc(sizeof(int)*n);
    list.len = n;
    printf("Random Number From 0 ~ %d\n", list.len);
    srand(time(0));
    for (int i = 0; i < list.len; ++i)
    {
        list.a[i] = rand() % list.len;
        printf("%d", list.a[i]);
        (i+1) % sps == 0 ? printf("\n") : printf("\t");
    }
    
    // bubbleSort_RE(list.a,list.len); // test pass
    // bubbleSort_NRE(list.a,list.len); // test pass

    // selectionSort_RE(list.a,list.len); // test pass
    // selectionSort_NRE(list.a,list.len); // test pass

    // insertionSort_RE(list.a,list.len); // test pass
    // insertionSort_NRE(list.a,list.len); // test pass

    // shellSort_NRE(list.a,list.len); // test pass
    
    // heapSort_NRE(list.a,list.len); // test pass

    // mergeSort_RE(list.a,list.len); // test pass

    quickSort_RE(list.a,list.len); // test pass

    printf("\nOrdered Sequence:\n");
    printlist(list.a, list.len, sps);

    free(list.a);

    exit(0);
}

接口的实现

#include "sort.h"
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// #include <time.h>

// used for heapSort
#define PARENT(i) (i >> 1)
#define LEFT(i)   (i << 1)
#define RIGHT(i)  (i << 1 + 1)

static const int MAX_INT = ((unsigned)(-1))>>1;
// static const int MIN_INT = ~MAX_INT;

static inline int Parent(int i) {return i >> 1;}
static inline int Left(int i) {return i << 1;}
static inline int Right(int i) {return ((i << 1) + 1);} 

// declaration of inner function
static int elemCompare(elem_t a, elem_t b);
static void swap(elem_t *a, int i, int j);
static bool makeMinToBeHead_BUB(elem_t *a, int n);
static void makeMinToBeHead_INS(elem_t *a, int n);
static void insertNewElem(elem_t *a, int n);
static void HeapAdjust(elem_t *a, int s, int m);
// 使根节点为i的子树维持最大堆的性质（前提：节点为i的左右子树都是最大堆）
static void MaxHeapify_RE(elem_t *a, int len, int i); 
static void MaxHeapify_NRE(elem_t *a, int len, int i);
static void BuildMaxHeap(elem_t *a, int len);
static void merge(elem_t *a,int p,int q,int r);
static void mergeSort(elem_t *a, int p, int r);
static void quickSort(elem_t *a, int p, int r);
static int patition(elem_t *a, int p, int r);

// ================================================================
// export function implementation
// ================================================================
extern void printlist(elem_t *a, int n, int sps){
    assert(a!=NULL);
    for (int i = 0; i < n; ++i)
    {
        printf("%d", a[i]);
        (i+1) % sps == 0 ? printf("\n") : printf("\t");
    }   
}
bool listCompare(List *a1, List *a2, int n){
    assert(a1!=NULL && a2!= NULL && n > 0);
    int index = 0;
    while(index++ < n && a1->a[index] == a2->a[index]){
        if (index == n-1)
        {
            return true;
        }
    }
    return false;
}
// 冒泡排序 最坏o(n^2)
extern void bubbleSort_RE(elem_t *a, int n){
    printf("\nUsing bubbleSort_RE Algorithm:\n");
    assert(a!=NULL);
    if (n < 2) return;
    else{
        if(true == makeMinToBeHead_BUB(a,n))
            bubbleSort_RE(a+1,n-1);
        else return;
    }
}

extern void bubbleSort_NRE(elem_t *a, int n){
    printf("\nUsing bubbleSort_NRE Algorithm:\n");
    assert(a!=NULL);
    bool flag = true; 
    // 检测是否已排序完成的标志，避免无意义的比较
    for (int i = 0; i < n && flag == true; ++i)
    {
        flag = false; 
        // 若内层循环无交换，则说明序列已排序
        for (int j = n-1; j > 0; --j)
        {
            if (elemCompare(a[j-1],a[j]))
            {
                swap(a,j-1,j);
                flag = true;
            }
        }
        // printf("%d\n", a[i]);
    }
}
// 选择排序 最坏o(n^2)
extern void selectionSort_RE(elem_t *a, int n){
    printf("\nUsing selectionSort_RE Algorithm:\n");
    assert(a!=NULL);
    if (n < 2) return;
    else{
        makeMinToBeHead_INS(a,n);
        selectionSort_RE(a+1,n-1);
    }
}
extern void selectionSort_NRE(elem_t *a, int n){
    printf("\nUsing selectionSort_NRE Algorithm:\n");
    assert(a!=NULL);
    for (int i = 0; i < n-1; ++i)
    {
        int min = i;
        for(int j = i+1; j < n; ++j)
        {
            if (elemCompare(a[min],a[j]))
            {
                min = j;
            }
        }
        if (min != i) //
        {
            swap(a,i,min);
        }
    }
}
// 插入排序 最坏o(n^2)
extern void insertionSort_RE(elem_t *a, int n){
    printf("\nUsing insertionSort_RE Algorithm:\n");
    assert(a!=NULL);
    if(n < 2) return;
    else{
        insertionSort_RE(a,n-1);// a[0]~a[n-2]为有序的
        insertNewElem(a,n); // 将a[n-1]插入到有序表
    }
}
extern void insertionSort_NRE(elem_t *a, int n){
    assert(a!=NULL);
    printf("\nUsing insertionSort_NRE Algorithm:\n");
    //=====================method 1====================
    for (int i = 1; i < n; ++i)
    {
        for(int j = i; j >= 1 && elemCompare(a[j-1],a[j]); --j)
            swap(a,j-1,j);
    }
    // =====================method 2====================
    // for (int i = 0; i < n; ++i)
    // {
    //  bool flag = true;
    //  for(int j = i+1; j > 0 && flag == true; --j)
    //  {
    //      flag = false;
    //      if (elemCompare(a[j-1],a[j]))
    //      {
    //          swap(a,j-1,j);
    //          flag = true;
    //      }
    //  }
    // }
}
// 希尔排序
extern void shellSort_RE(elem_t *a, int n){

}
extern void shellSort_NRE(elem_t *a, int n){
    printf("\nUsing shellSort_NRE Algorithm:\n");
    assert(a!=NULL);
    // int loopCnt = 0; // for debug
    for(int increment = n/2; increment >= 1; increment = increment/2){
        // printf("\nLoop %d, increment = %d:\n", loopCnt++, increment);
        for(int i = increment; i < n; ++i){
            // printf("\ni = %d\n", i);
            for(int j = i; j >= increment && elemCompare(a[j-increment],a[j]); j -= increment)
            {
                // printf("%d and %d will be swaped\n", a[j-increment],a[j]);
                swap(a,j-increment,j);
            }
            // printlist(a,n,10);
        }
    }
}
// 堆排序（简单选择排序的改进）
extern void heapSort_RE(elem_t *a, int n){
    
}
extern void heapSort_NRE(elem_t *a, int n){
    assert(a!=NULL && n > 0);
    printf("\nUsing heapSort_NRE Algorithm:\n");
    //===================method 2 算法导论==================
    BuildMaxHeap(a,n);  // 构建最大堆
    for(int i = n-1; i >=1; i--){
        swap(a,0,i);
        MaxHeapify_NRE(a,i,0); 
        // 维护最大堆, 每循环一次，需要维护的堆的大小减一
        // 维护以偏移量为0的元素为根的大小为i的堆为最大堆
    }

    //===================method 1 大话数据结构==================
    // for (int i = n/2; i > 0; i--)
    // {
    //  HeapAdjust(a,i,n);
    // } // 构建最大堆// 维护最大堆
    // for(int i = n; i > 1; i--)
    // {
    //  swap(a,0,i-1);
    //  HeapAdjust(a,1,i-1);
    // }// 维护最大堆

}
// 归并排序
extern void mergeSort_RE(elem_t *a, int n){
    printf("\nUsing mergeSort_RE Algorithm:\n");
    assert(a!=NULL && n >= 0);
    int p = 0, r = n-1;
    mergeSort(a,p,r);
}
extern void mergeSort_NRE(elem_t *a, int n){
    
}
// 快速排序（冒泡排序的改进）
extern void quickSort_RE(elem_t *a, int n){
    printf("\nUsing quickSort_RE Algorithm:\n");
    assert(a!=NULL && n >= 0);
    int p = 0, r = n-1;
    quickSort(a,p,r);
}
extern void quickSort_NRE(elem_t *a, int n){

}
// ================================================================
// inner function implementation
// ================================================================
static int elemCompare(elem_t a, elem_t b){
    return (a > b);
}

static void swap(elem_t *a, int i, int j){
    assert(a!=NULL);
    int temp = a[j];
    a[j] = a[i];
    a[i] = temp;
}

bool makeMinToBeHead_BUB(int *a, int n){
    assert(a!=NULL);
    bool flag = false;
    for (int i = n-1; i > 0; i--)
    {
        if (elemCompare(a[i-1],a[i]))
        {
            swap(a,i-1,i);
            flag = true;
        }
    }
    return flag;
}

static void makeMinToBeHead_INS(elem_t *a, int n){
    assert(a!=NULL);
    int min = 0;
    for (int i = 1; i < n; ++i)
    {
        if (elemCompare(a[min],a[i]))
        {
            min = i;
        }
    }
    if (min != 0)
    {
        swap(a,min,0);
        // printf("%d\n", a[0]);
    }
}

static void insertNewElem(elem_t *a, int n){
    assert(a!=NULL);
    // printf("\n%d will be inserted.\n", a[n-1]); // for debug
    bool flag = true; // 插入成功标志
    for (int i = n-1; i > 0 && (flag == true); --i) // 再也不要用代码自动生成功能 --i
    {
        flag = false;
        if (elemCompare(a[i-1],a[i]))
        {
            // printf("to swap %d and %d\n",a[i-1],a[i]); // for debug
            swap(a,i-1,i);
            flag = true;
        }
    }
    // printlist(a,n,10); // for debug
    // printf("\n"); 
}

static void HeapAdjust(elem_t *a, int s, int m){
    assert(a!=NULL && s > 0 && m > 0);
    int temp = a[s-1];
    for(int j = 2*s; j <= m; j *=2)
    {
        if(j < m && elemCompare(a[j],a[j-1]))
            ++j;
        if(elemCompare(temp,a[j-1]))
            break;
        a[s-1] = a[j-1];
        s = j;
    }
    a[s-1] = temp;
}
// 维持一个最大堆，最坏时间复杂度O(log(n))
static void MaxHeapify_RE(elem_t *a, int len, int i){
    assert(a!=NULL && len >= 0 && i >=0 && i < len);
    // i是当前节点的偏移量，i+1是当前节点的层序编号
    // lchild是孩子节点的偏移量，lchild + 1是孩子节点的层序编号
    // 对于完全二叉树，有关系lchild + 1 = Left(i+1)
    int lchild = Left(i+1) - 1; 
    int rchild = Right(i+1) - 1;
    // 临时设置最大值节点的偏移量为当前节点值
    int largest = i;

    // 在有左孩子的前提下（lchild < len），将当前节点值与左孩子节点值比较
    if(lchild < len && elemCompare(a[lchild],a[largest]))
        largest = lchild;
    // 在有左孩子的前提下（lchild < len），将当前节点值与左孩子节点值中的较大值与右孩子节点值比较
    if(rchild < len && elemCompare(a[rchild], a[largest]))
        largest = rchild;

    if (largest != i){
        swap(a,i,largest);
        MaxHeapify_RE(a,len,largest);
    }
}

static void MaxHeapify_NRE(elem_t *a, int len, int i){
    assert(a!=NULL && len >= 0 && i >=0 && i < len);
    int root = i;
    while(root < len){
        int lchild = Left(root+1) - 1; 
        int rchild = Right(root+1) - 1;
        int largest = root;
        
        if(lchild < len && elemCompare(a[lchild],a[largest]))
            largest = lchild;
        if(rchild < len && elemCompare(a[rchild], a[largest]))
            largest = rchild;

        if (largest == root)
            break;
        else {
            swap(a,root,largest);
            root = largest; // 沿着未调整前较大孩子节点的子树往下调整
        }
    }
}
// 讲一个无序数组构建成一个最大堆，最坏时间复杂度为O(n)
static void BuildMaxHeap(elem_t *a, int len){
    assert(a!=NULL && len >= 0);
    for(int i = Parent(len)-1; i >= 0; i--){
        MaxHeapify_NRE(a,len,i);
    }
}
static void mergeSort(elem_t *a, int p, int r){
    assert(a!=NULL && p >= 0 && r >=0 && r >= p);
    if(p < r){
        int q = ((p+r) >> 1);
        mergeSort(a,p,q);
        mergeSort(a,q+1,r);
        merge(a,p,q,r);
    }
}
// 合并两个有序的子序列为一个有序序列
static void merge(elem_t *a,int p,int q,int r){
    assert(a!=NULL && p >= 0 && q >= 0 && r >=0 && q >=p && r >= q);
    int nl = q - p + 1; // len1
    int nr = r - q;     // len2
    int L[nl+1],R[nr+1];
    for(int i = 0; i < nl; i++){
        L[i] = a[p+i];
    }
    for (int j = 0; j < nr; ++j){
        R[j] = a[q+j+1];
    }
    L[nl] = MAX_INT;
    R[nr] = MAX_INT;
    int i = 0, j = 0;
    // O(n), n = r - p + 1
    for(int k = p;k <= r;k++){
        if(elemCompare(L[i],R[j])){
            a[k] = R[j];
            j++;
        }
        else{
            a[k] = L[i];
            i++;
        }
    }
}
// static int cnt = 0;
static void quickSort(elem_t *a, int p, int r){
    assert(a!=NULL);
    // printf("\nNo.%05d p = %d, r = %d\n", ++cnt,p,r);
    if(p < r){
        int q = patition(a,p,r);
        // printf("\nNo.%05d p = %d, q = %d, r = %d\n", ++cnt,p,q,r);
        quickSort(a,p,q-1);
        quickSort(a,q+1,r);
    }
}
static int patition(elem_t *a, int p, int r){
    assert(a!=NULL && p >= 0 && r >=0 && r >= p);
    //x取子数组最后一个元素，把比x小的放在左边， 把比x大放到右边
    elem_t x  = a[r]; 
    int i = p - 1;
    for(int j = p; j <= r-1; j++){
        if (elemCompare(x,a[j])) // a[j] <= x
        {
            swap(a,++i,j);
        }
    }
    swap(a,i+1,r);
    return (i+1);
}

最后编辑于：2018.06.23 00:56:12

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,456评论 5赞 477
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,370评论 2赞 381
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 150,337评论 0赞 337
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,583评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,596评论 5赞 365
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,572评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,936评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,595评论 0赞 258
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,850评论 1赞 297
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,601评论 2赞 321
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,685评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,371评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,951评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,934评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,167评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 43,636评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,411评论 2赞 342

算法基础：6种经典排序算法的递归和非递归实现

接口

测试代码

接口的实现

推荐阅读更多精彩内容