个性化阅读
专注于IT技术分析

9大经典排序算法原理和实现代码详解

上一节我们讨论了优先队列和堆的原理和实现,其中堆可用于排序,称为堆排序(heap sort)。本节详细讨论9大经典排序算法,排序算法可以说是我们开发中的一种基本算法,而用到最多的则是快速排序(quick sort),它适用于一般情形,但并不都是最优的,本节还介绍其它算法,某些情况下会比快排好,另外排序算法也是面试中经常遇到的题目(下面介绍的排序算法若无特殊情况一般都是以升序为准)。

一、排序算法的基本概念

排序算法中基本的数据类型是数组,排序的依据可使用简单的数字、字母或字符串。排序的数组大小为n,如果n较小(如小于10^6),则可以在主存中进行排序,又称为内排序,如果n较大,则需要在磁盘上和主存中完成排序,又称为外排序(external sorting)。

整体来说,排序算法又分为两种:基于比较的排序和非比较排序,基于比较的排序使用>大于号、<小于号对两个数进行比较,例如有选择、插入、冒泡排序等,另一种是非比较的排序,如桶排序、基数排序和计数排序,非比较排序一般比较快,使用空间换取时间,下图是完整的排序算法分类(来自网络):

排序算法完整分类

排序算法另一个需要关注的是算法的稳定性,在数组中a在b的前面,并且a=b,若排序后a在b前面,则称该算法稳定,若排序后a在b后面,则称该算法不稳定,至于在实际使用中是否需要考虑排序算法的稳定性,那要看需求(例如预先分析数据是有重复的),像平时我们使用的快速排序则是没有考虑,下图是所有排序算法的复杂度和稳定性的图表(来自网络):

所有排序算法的复杂度和稳定性图表

二、选择排序(selection sort)

选择排序是比较简单的排序算法(另外有选择排序的实现原理及其应用详解),其最坏情况为O(n^2),它的算法是:迭代地找出数组右边未排序部分的最小值,将最小值放在左边,动画演示:

选择排序算法动画演示

选择排序算法代码实现:

static void swap(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

void selection_sort(int array[], int n){
    int i, j, temp;
    for (i = 0; i < n; ++i) {
        temp = i;
        for (j = i + 1; j < n; ++j) {
            if(array[j] < array[temp])
                temp = j;
        }
        swap(&array[i], &array[temp]);
    }
}

三、冒泡排序(bubble sort)

冒泡排序的时间为O(n^2),也是一个相当简单的基于比较的排序算法,它通过比较相邻的元素,每一轮比较得出一个较大值,将该较大值移到右边,冒泡算法的动画演示如下:

冒泡算法动画演示

下图是冒泡算法的静态演示例子:

冒泡排序算法图解

冒泡排序算法实现如下:

void bubble_sort(int array[], int n){
    int i, j;
    for (i = 0; i < n - 1; ++i) {
        for (j = 0; j < n - 1 - i; ++j) {
            if(array[j] > array[j + 1])
                swap(&array[j], &array[j + 1]);
        }
    }
}

四、插入排序(insertion sort)

插入排序的最坏时间和平均时间都是O(n^2),插入排序算法从第1个元素开始到第n-1个元素,将当前元素和左边的元素进行比较,持续向左比较相距间隔为1的元素,直到遇到比移动元素小的元素。

在数组A中,满足条件i<j,A[i]>A[j]的两个元素称为逆序对,此时排序算法的运行时间为O(I + n),其中I为数组A的逆序数(逆序对的数量),n个互异数的数组的平均逆序数为n(n-1)/4,因而,通过交换相邻元素进行排序的任何算法平均时间为Ω(n^2)(确定的下界)。

插入排序的算法动画演示如下:

插入排序动画演示

下图是插入排序的静态演示实例:

插入排序实例图解

插入排序实现代码如下:

void insertion_sort(int array[], int n){
    int i, j, temp;
    for (i = 1; i < n; ++i) {
        temp = array[i];
        for (j = i; j > 0 && array[j - 1] > temp; --j) {
            array[j] = array[j - 1];
        }
        array[j] = temp;
    }
}

五、希尔排序(shellsort)

希尔排序的时间为O(n^2),希尔排序是插入排序的一个推广,插入排序是向左边每间隔1个元素比较一次,希尔排序则更灵活,使用一个增量序列h1, h2, …, ht(其中h1=1)对元素进行比较,因而希尔排序又叫做缩小增量排序,对于增量排序,第一步是确定增量函数,例如k(k-1)=hk/2,再确定一个初始化值,如hk=m,使用增量hk的一趟排序后相隔hk的元素都被排序,此时A[i] <= A[i + hk]。常见的增量序列有希尔增量:hk=n/2,Hibbard增量:hk=n/2,hk为奇数,hk为偶数时,hk=hk-1。

其中较好的增量序列为{1, 5, 19, 41, 109, …},通项为9*4^i – 9*2^i + 1或4^i – 3*2^i + 1,希尔排序的关键是在于增量序列,当前也还有其它增量序列。

希尔排序的性质如下:

  1. hk-排序后序列保留hk-排序性;
  2. 使用希尔增量时希尔排序的最坏情况为O(n^2);
  3. 使用Hibbard增量的希尔排序的最坏情况为O(n^(3/2))。

希尔排序的算法如下:

  1. 确定增量函数(增量序列的选择),例如,初始增量使用ht=n/2,增量递减hk=(k+1)/2,h1=1;
  2. 每次比较从初始增量ht开始,将A[i]和A[i-ht]的元素进行比较,比较到最后一个增量的位置。

希尔排序的动画演示如下:

希尔排序动画演示

下面是希尔排序的一个实例:

希尔排序算法实例图解

希尔排序算法实现如下:

void shell_sort(int array[], int n){
    int i, j, temp, gap;
    for (gap = n / 2; gap > 0; gap /= 2) {
        for (i = gap; i < n; ++i) {
            temp = array[i];
            for (j = i; j >= gap && array[j - gap] > temp; j -= gap) {
                array[j] = array[j - gap];
            }
            array[j] = temp;
        }
    }
}

六、堆排序(heap sort)

上一节我们讨论过优先队列和堆,对于堆排序其最差情况为O(nlog n),但是慢于Sedgewick增量的希尔排序。堆排序使用二叉堆使用,使用数组表示,如果纯属使用二叉堆数据结构,则对数组进行排序需要使用辅助的数组,但是这里堆排序不使用第二个数组,将先出队的元素放到数组末尾,由于放置元素是从结尾到开头,所以,如果是降序则使用最小堆,升序使用最大堆。

对n个互异的随机序列进行堆排序,所用的平均比较次数为2nlog n – O(nlog n)。

堆排序的算法如下:

  1. 构造最大堆(堆化操作),进行下滤操作;
  2. 先构建好堆,对前n/2个元素进行下滤操作;
  3. 进行n-1次出队操作,将出队的元素放到数组结尾。

堆排序的动画演示如下:

堆排序动画演示

下图是另一个堆排序的实例:

堆排序算法图解

堆排序实现算法如下:

static void heapify(int array[], int i, int n){
    int left, child, temp = array[i];
    while((left = 2 * i + 1) < n){
        child = left;
        if(left + 1 < n && array[left + 1] > array[left])
            child = left + 1;
        if(array[child] > temp)
            array[i] = array[child];
        else
            break;
        i = child;
    }
    array[i] = temp;
}

void heap_sort(int array[], int n){
    for (int i = n / 2; i >= 0; --i)
        heapify(array, i, n);
    for (int j = n - 1; j > 0; --j) {
        swap(&array[0], &array[j]);
        heapify(array, 0, j);
    }
}

七、归并排序(merge sort)

归并排序的最差情况为O(nlog n),归并即是递归和合并的意思,虽然其效果不是很好,但是其排序思想却比较重要,例如下面的快速排序和外部排序都是用到其递归和合并的思想。

归并排序的算法如下:

  1. 归并排序的主要目的是合并两个已经排好序的数组;
  2. 首先新建一个和原数组同样大小的辅助数组;
  3. 对从0到n-1的元素进行分组和合并,分界点为center=(left+right)/2,对左右两部分再次进行分组,最后再合并两部分。

归并排序的缺点是需要附加线性内存,需要将数据拷贝到临时数组再拷贝会原数组,归并排序算法的实例如下:

归并排序算法实例图解

下面是归并排序的算法演示:

归并排序算法演示

归并排序的算法实现代码如下:

static void merge(int array[], int temp[], int ls, int rs, int re){
    int le =  rs - 1, t = ls, count = re - ls + 1;
    while(ls <= le && rs <= re){
        if(array[ls] <= array[rs]){
            temp[t] = array[ls];
            ls++;
            t++;
        }
        else{
            temp[t] = array[rs];
            rs++;
            t++;
        }
    }
    while(ls <= le){
        temp[t] = array[ls];
        ls++;
        t++;
    }
    while(rs <= re){
        temp[t] = array[rs];
        rs++;
        t++;
    }
    for (int i = count; i > 0; --i, re--) {
        array[re] = temp[re];
    }
}

static void msort(int array[], int temp[], int left, int right){
    if(left < right){
        int center = (left + right) / 2;
        msort(array, temp, left, center);
        msort(array, temp, center + 1, right);
        merge(array, temp, left, center + 1, right);
    }
}

void merge_sort(int array[], int n){
    int *temp = (int*)malloc(sizeof(int) * n);
    if(temp){
        msort(array, temp, 0, n - 1);
        free(temp);
    }
    else{
        perror("alloc memory for temp array error");
    }
}

八、快速排序(quick sort)

快速排序是目前最快的已知排序算法,但是要注意它的最坏情况为O(n^2),平均运行时间为O(nlog n),快速排序算法的操作方式和上面的归并排序很像,它的算法描述如下:

  1. 使用递归算法处理数组S,如果S的长度为0或1,返回;
  2. 在S中任取一个元素pivot,pivot成为枢纽元素,枢纽元素是数组元素数值上的一个值;
  3. 使用这个枢纽元素将S分割为S1,pivot,S2,按照大于、小于或等于pivot的值,对S进行分割,对于等于pivot的元素,一半放到S1,一半放到S2中;
  4. 然后对S1、S2分别递归地执行1-3步;
  5. 执行到最后,S则是已排好序的数组。

下图是快速排序的一个例子:

快速排序图解

下面向下说一下快速排序算法的细节:

1、选取枢纽元素pivot

(1)不建议使用的方法,使用第一个元素作为枢纽元素,或者使用前两个最大者作为枢纽元素,虽然该方法很快捷,但是有可能造成快排效率较低;

(2)安全的方法,随机选取枢纽元,但是生成随机数昂贵,而且不能保证有更好的算法效率;

(3)三数中值分割法,选取最左最右元素和中间元素:left、right和(left+right)/2,选取中间值的元素作为枢纽元素,推荐使用该方法,下面的实现使用该方法。

2、分割策略

(1)将枢纽元素移到数组的结尾,i从第一个元素开始,j从倒数第二个元素开始;

(2)以枢纽元素为参照,将最小元素移到数组左边,将最大元素移到数组右边;

(3)移动元素和交换元素:

a、i右移动,跳过小于pivot的元素,遇到大于pivot的元素停止,此时位置为k;

b、j左移动,跳过大于pivot的元素,遇到小于pivot的元素停止,此时位置为m,交换位置为k和m的元素;

c、i和j停止时,i指向大元素,j指向小元素,如果i在j的左边,交换这两个元素,否则不用交换;

d、最后将i指向的元素和枢纽元素进行交换。

(4)处理元素等于pivot时的情况:让i和j都停止,进行交换。

在经过以上处理一趟后,此时对于P>i的元素都是大元素,P<i的元素都是小元素。

注意,在这里如果n过小(n<=20),小数组的情况,插入排序的效率会比快排好,可在n<=10时,使用插入排序,下图是快速排序的算法动画演示:

快速排序算法演示

根据以上的描述,排序算法的实现,大概的步骤如下:

  1. 创建n<=10的条件,该条件下使用插入排序;
  2. 选取枢纽元素pivot,参考left、right、(left+right)/2,比较这三个位置的元素,以符合A[left] <= A[center] <= A[right],选取A[center]为pivot枢纽元素。将pivot=A[center]放到A[right-1]上(因为pivot = A[center] <= A[right]),分割时j=right-2;
  3. 分割数组,其实就是递归执行以上步骤;
  4. 对左右部分递归调用处理。

以上的递归算法也可以解决选择问题,也就是选取第k个最大或最小的元素,算法和快速排序算法是一样的,但是只需要一次递归。

对于排序的一般下界:

  • 只使用元素间比较的任何排序算法在最坏情况下至少需要log(n!)次比较;
  • 只使用元素间比较的任何排序算法需要进行Ω(nlog n)次比较;

信息理论的下界:存在P种不同的情况需要区分的问题,问题仅仅是YES/NO的形式,那么求解该问题需要logP个问题,这里是对比较排序算法的一些结论。

快速排序的代码实现:

static int get_pivot(int array[], int left, int right){
    int center = (left + right) / 2;
    if(array[left] > array[center])
        swap(&array[left], &array[center]);
    if(array[left] > array[right])
        swap(&array[left], &array[right]);
    if(array[center] > array[right])
        swap(&array[center], &array[right]);
    swap(&array[right - 1], &array[center]);
    return array[right - 1];
}


static void QSort(int array[], int left, int right){
    if(left + 3 <= right){
        int i, j, pivot;
        pivot = get_pivot(array, left, right);
        i = left, j = right - 1;
        while(1){
            while(array[++i] < pivot){}
            while(array[--j] > pivot){}
            if(i < j)
                swap(&array[i], &array[j]);
            else
                break;
        }
        swap(&array[i], &array[right - 1]);
        QSort(array, left, i - 1);
        QSort(array, i + 1, right);
    }
    else
        insertion_sort(array + left, right - left + 1);
}

void quick_sort(int array[], int n){
    QSort(array, 0, n - 1);
}

九、桶排序(bucket sort)

桶排序和计算排序、基数排序是类似的,这里介绍具有代表性的桶排序,桶排序的时间为O(m+n),m为数组中的最大元素,桶排序的算法的描述如下:

  1. 新建一个数组Q,长度为m,其中A[i]<m,也是最大元素加1,将Q初始化为0;
  2. 扫描A,使得Q[A[i]]=1;
  3. 扫描数组Q,打印为1的索引即为排序结果。

注意,一般的桶排序算法不能用于小于0的数组,桶排序实现算法如下:

void bucket_sort(int array[], int n){
    int max = array[0], i;
    for (i = 1; i < n; ++i) {
        if(array[i] > max)
            max = array[i];
    }
    max++;
    int temp[max];
    for (int k = 0; k < max; ++k) {
        temp[k] = 0;
    }
    for (int j = 0; j < n; ++j) {
        temp[array[j]]++;
    }
    int j = 0;
    for (int l = 0; l < max; ++l) {
        while(temp[l] > 0){
            array[j++] = l;
            temp[l]--;
        }
    }
}

十、外部排序(external sorting)

上面介绍都是内部排序,可以直接在主存中执行排序,外排序适合数据量太大而无法装入内存的情况,这时需要将数据装进磁盘或外存,对外存中的数据进行排序。以上的排序算法都是可以直接到内存中寻址,但是直接使用以上的排序算法,对外存数据排序会造成过多IO读取次数,严重损失效率。

外部排序算法整体来说分为两步:构造顺串和合并排序,顺串(run)指定是一个已排好序的序列,构造顺串指的是在初始阶段读取原始数据构造一个个的顺串,合并排序指的是将k个顺序进行合并排序,合并成一个排好序的文件,下面介绍的简单算法、多路合并和多相合并都是合并算法,后面的替换选择是构造顺串的算法。

1、简单算法

执行的IO时间需要log(n/m)趟工作,m为顺串的长度。简单算法是2路合并,2个输入磁带,2个输出磁带,一共4个磁带。设a、b磁带为输入磁带,程序输入已排好序的数据到磁带上,c、d磁带为输出磁带,输出数据到程序进行排序,详细算法如下:

  1. 每次从a、b磁带读取m个数据,读入到程序并进行排序,排序的算法可使用归并排序的算法,这时排好序的m个数据称为一个顺串;
  2. 将每个顺串写到c、d磁带上,再分别读取c、d的一组数据进行合并排序,排好序写入a、b;
  3. 重复以上过程,直到c、d为空,或只剩下一个顺串,则拷贝到适当的顺串上。

下面是使用简单算法的一个例子:

外部排序简单算法图解

2、多路合并

多路合并也就是上面2路合并的扩展,也是k路合并,这时一共需要2k个磁带,k个输入磁带,k个输出磁带。IO时间,趟树为log(n/m),底数为k,算法过程和以上简单算法类似,可借助优先队列实现。

3、多相合并

多相需要的磁带数为k+1,设有3个磁带,a上有34个顺串:

  1. 初始化将b写入21个顺串,c为13个;
  2. b和c合并写入a,a为13个,b为8个,c为0个;
  3. a和b合并写入c,a为5个,b为0个,c为8个;
  4. 依此操作,直到一个磁盘上只有一个顺串。

如果顺串的个数是斐波那契数,那么最优的分配为:k+1个磁盘,分为k个斐波那契数。

4、替换选择

替换选择算法是顺串的产生算法,在初始化顺串的时候使用,后面使用归并排序中的合并操作进行合并,详细算法如下:

  1. 读入m个数据,存到优先队列,优先队列的元素个数为m;
  2. 执行出队操作,将最小元素写到输出磁带上;
  3. 继续从输入磁带读入数据,如果比前一个写入的元素大,加入优先队列,执行出队操作,写入输出磁带;
  4. 如果读入的促进比前一个写入的小,则将新元素存入优先队列的死区(就是优先队列的结尾),用于下一个顺串,同时也进行出队操作,写入输出磁带;
  5. 依此操作,直到优先队列的元素个数为0,这时使用死区的元素重新构建一个新的优先队列;

下面是构造顺串的一个例子:

替换选择构造顺串实例

5、外部排序算法实现

外部排序的主要策略是先排序构造顺串,后合并排序,排序构造顺串的步骤是:先读取文件数据进行排序,每次读取一个顺串大小的数据,使用归并排序对每个顺串进行排序,将每个已排序的顺串保存到临时文件,此时一共有k个临时文件或顺串。

后合并排序步骤是:将已排好序的文件合并成一个大文件,也就是k路归并,合并k个已排序的顺串。外部排序的主要算法如下:

  1. 设输入输出文件名为input和output,output文件合并后的结果文件;
  2. 确定待排序文件顺串的数量k,顺串的最大长度size(测试方便,可生成一个k*size个数据的文件);
  3. 创建初始化顺串。创建k个临时文件,创建size大小的数组进行处理数据,每次从文件读取size个数据记录,调用归并排序,将排好序的顺串保存在k个临时文件中;
  4. 合并文件。也就是k路归并,打开k个临时文件(k个顺串),创建大小为k的最小堆,分别使用k个顺串的第一个元素进行初始化,然后迭代地陆续将最小元素出队,并保存到输出文件中,到此外部排序完成

在以上描述中我们可以看到,外部排序,首先在构造顺串的时候需要使用归并排序,而在合并文件的时候需要使用优先队列,下面是实现外部排序的声明代码:

typedef struct heapnode{
    int data;
    int i; // 第i个顺串中的数据记录
} HeapNode;

// 二叉堆(最小堆)
typedef struct heap{
    HeapNode *array;
    int size;
} Heap;

// 优先队列主要使用到的操作
extern Heap *heap_new(HeapNode *datas, int size);
extern HeapNode *heap_min(Heap *heap);
extern void heap_replace_min(Heap *heap);

// 交换数据记录
extern void swap(HeapNode *a, HeapNode *b);

// 归并排序
extern void msort(int array[], int left, int right);

// 外部排序
extern void external_sort(char *input, char *output, int runs, int run_size);

extern FILE* openFile(char* fileName, char* mode);

其完整代码可以在github上查看,其中sorting.h是所有的内部排序算法,esorting.h是外部排序算法:https://github.com/onnple/sortingalgorithms,main.c提供使用实例。

赞(0) 打赏
未经允许不得转载:srcmini » 9大经典排序算法原理和实现代码详解
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!

 

觉得文章有用就打赏一下文章作者

微信扫一扫打赏