各种基本排序算法的总结

On September 25, 2010, in 算法, 笔试面试, 数据结构, by sponge

本文是为了加深自己对各种算法的理解,部分摘自维基百科,这里主要介绍较为常用的排序方法,一些生僻的算法不做介绍。
.
总结各种算法之前,现介绍下几个概念:
1、稳定度:稳定排序算法会依照相等的关键(换言之就是值)维持纪录的相对次序。也就是一个排序算法是稳定的,就是当有两个有相等关键的纪录R和S,且在原本的串行中R出现在S之前,在排序过的串行中R也将会是在S之前。
2、计算的复杂度(最差、平均、和最好表现),依据串行(list)的大小(n)。一般而言,好的表现是O(n log n),且坏的行为是O(n2)。对于一个排序理想的表现是O(n)。仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要O(n log n)。
.
稳定排序:
* 泡沫排序(bubble sort) — O(n²)
* 插入排序 (insertion sort)— O(n²)
* 桶排序 (bucket sort)— O(n); 需要 O(k) 额外空间
* 计数排序 (counting sort) — O(n+k); 需要 O(n+k) 额外空间
* 合并排序 (merge sort)— O(n log n); 需要 O(n) 额外空间
* 二叉排序树排序 (Binary tree sort) — O(n log n)期望时间; O(n²)最坏时间; 需要 O(n) 额外空间
* 基数排序 (radix sort)— O(n·k); 需要 O(n) 额外空间
.
不稳定排序
* 选择排序 (selection sort)— O(n²)
* 希尔排序 (shell sort)— O(n log n) 如果使用最佳的现在版本
* 堆排序 (heapsort)— O(n log n)
* 快速排序 (quicksort)— O(n log n) 期望时间, O(n2) 最坏情况; 对于大的、乱数串行一般相信是最快的已知排序
.
排序的算法有很多,对空间的要求及其时间效率也不尽相同。下面列出了一些常见的排序算法。这里面插入排序和冒泡排序又被称作简单排序,他们对空间的要求不高,但是时间效率却不稳定;而后面三种排序相对于简单排序对空间的要求稍高一点,但时间效率却能稳定在很高的水平。基数排序是针对关键字在一个较小范围内的排序算法。
.
这篇文章里,将对几种基础排序介绍,包括冒泡排序、插入排序、选择排序、快速排序。稍微复杂些的排序留在二中介绍。
.
<<<<<<<<<<<<<<<<<<<<<<<分割线>>>>>>>>>>>>>>>>>>>>>>>>>>>>
.
1、冒泡排序
冒泡排序是一种简单的排序方法,算法如下:
1. 首先将所有待排序的数字放入工作列表中。
2. 从列表的第一个数字到倒数第二个数字,逐个检查:若某一位上的数字大于他的下一位,则将它与它的下一位交换。
3. 重复2号步骤(倒数的数字加1。例如:第一次到倒数第二个数字,第二次到倒数第三个数字,依此类推...),直至再也不能交换。
用C语言实现如下:

int BubbleSort(int *a, int b){ //a是待排序的整型数组
                                       //b是待排序数组的元素个数
    int i;
    int temp;
    for(i = b-1; i>=0; i++){
        if(a[i]>a[i+1]){
            temp = a[i+1];
            a[i+1] = a[i];
            a[i] = temp; //交换元素
        }
    }

最差时间复杂度 O(n²)
最优时间复杂度 O(n)
平均时间复杂度 O(n²)
最差空间复杂度 O(n) total, O(1) auxiliary

.
2、插入排序
插入排序也是一种简单排序方法,算法如下:
1. 从第一个元素开始,认为该元素已经是排好序的。
2. 取下一个元素,在已经排好序的元素序列中从后向前扫描。
3. 如果已经排好序的序列中元素大于新元素,则将该元素往右移动一个位置。
4. 重复步骤3,直到已排好序的元素小于或等于新元素。
5. 在当前位置插入新元素。
6. 重复步骤2。
用C实现如下:

int InsertSort(int *a, int b){
    int i,j;
    int temp;
    for(i = 0; i< b; i++){
         temp = a[i];
         for(j = i-1; j>=0; j--){
            if(a[j] > temp)
                a[j+1] = a[j]; //将元素往右移动
            else{
                a[j+1]=temp;
                break;
            }
        }
    }

最差时间复杂度 O(n²)
最优时间复杂度 O(n)
平均时间复杂度 O(n²)
最差空间复杂度 O(n) total, O(1) auxiliary

.

3、选择排序
选择排序的思想如下:
1. 设数组内存放了n个待排数字,数组下标从1开始,到n结束。
2. i=1
3. 从数组的第i个元素开始到第n个元素,寻找最小的元素。(具体过程为:先设arr[i]为最小,逐一比较,若遇到比之小的则交换)
4. 将上一步找到的最小元素和第i位元素交换。
5. 如果i=n-1算法结束,否则回到第3步
用C语言实现如下:

int SelectSort(int *a, int b){
    int i,j;
    int flag; //用于记录哪个元素最小
    int temp;
    for(i = 0; i< b; i++){
        flag = i;
        for(j = i+1; j a[j]){
                flag = j;
            } //选出从i开始最小的元素
        }
        temp = a[flag];
        a[flag] = a[i];
        a[i] = temp;  //交换元素
    }

最差时间复杂度 О(n²)
最优时间复杂度 О(n²)
平均时间复杂度 О(n²)
最差空间复杂度 О(n) total, O(1) auxiliary

.
以上三种排序的时间复杂度都是O(n²)。
.
4、快速排序
实践证明,快速排序是所有排序算法中最高效的一种。它采用了分治的思想:先保证列表的前半部分都小于后半部分,然后分别对前半部分和后半部分排序,这样整个列表就有序了。
快速排序的基本算法是:
1. 从数列中挑出一个元素,称为 "基准"(pivot),
2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割之后,该基准是它的最后位置。这个称为分割(partition)操作。
3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
递回的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递回下去,但是这个算法总会结束,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
用C语言实现如下:

void swap(int *a, int *b)
{ 
    int t=*a; *a=*b; *b=t; 
}
int QuickSort(int *a, int b){
    int i, j;
    int base;
    if(b>1){
        base = a[0]; //设第一个元素为基准
        i = 1; j = b-1;
        while(i<j){
            if(a[i]<base)
                i++;
            else
                swap(&a[i],&a[j--]);//如果i位置的数大于基准,则往后移                
        }
        if(a[i]<base){ //将基准插入到中间
            swap(&a[0], &a[i]);
            QuickSort(a, i+1);
            QuickSort(&a[i+1], b-i-1);
        }
        else{
            swap(&a[0], &a[i+1]);
            QuickSort(a, i);
            QuictSort(&a[i],b-i);
        }
    }
}

快速排序的时间复杂度是O(nlogn),但是最坏情况下复杂度是O(n²)。
最差时间复杂度 Θ(n²)
最优时间复杂度 Θ(nlogn)
平均时间复杂度 Θ(nlogn) comparisons
最差空间复杂度 根据实现的方式不同而不同

.

anyShare分享到:

7 Responses to “各种基本排序算法的总结”

  1. littlebeauty says:

    这个我学过,我知道,哈哈

  2. zhown says:

    这篇的插入排序错了

    看了你空间里很多的文章,感觉真的是受益匪浅...希望可以创作更多...
    学习ing...

  3. bborn says:

    很显然冒泡错了

  4. Niko says:

    冒泡排序错吧,比较明显。

  5. I think the admin of this web page is genjuinely working hard for hiss web site, because here every material
    is quality based information.

Leave a Reply to bborn

Note: Commenter is allowed to use '@User+blank' to automatically notify your reply to other commenter. e.g, if ABC is one of commenter of this post, then write '@ABC '(exclude ') will automatically send your comment to ABC. Using '@all ' to notify all previous commenters. Be sure that the value of User should exactly match with commenter's name (case sensitive).