排序算法总结

fishlife

浏览: 4847 次
性别:
来自: 广州

最近访客更多访客>>

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

算法

算法 J#Exchange

首先是来自WIKI上的一些分类总结：

穩定的

泡沫排序（bubble sort） — O(n ² )
鸡尾酒排序 (Cocktail 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 ) 額外空間
原地合併排序 — O(n ² )
二叉排序树排序（Binary tree sort） — O(n log n )期望时间; O(n ² )最坏时间; 需要 O(n ) 額外空間
鸽巢排序 (Pigeonhole sort) — O(n +k ); 需要 O(k ) 額外空間
基數排序（radix sort）— O(n ·k ); 需要 O(n ) 額外空間
Gnome sort — O(n ² )
Library sort — O(n log n ) with high probability, 需要 (1+ε)n 額外空間

[编辑 ] 不穩定

選擇排序（selection sort）— O(n ² )
希爾排序（shell sort）— O(n log n ) 如果使用最佳的現在版本
Comb sort — O(n log n )
堆排序（heapsort）— O(n log n )
Smoothsort — O(n log n )
快速排序（quicksort）— O(n log n ) 期望時間, O(n ² ) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序
Introsort — O(n log n )
Patience sorting — O(n log n + k ) 最坏情況時間，需要額外的 O(n + k ) 空間，也需要找到最長的遞增子序列（longest increasing subsequence）

常用的八种排序的对比

排序法	平均时间	最差情形	稳定度	额外空间	备注
冒泡	O(n² )	O(n² )	稳定	O(1)	n 小时较好
交换	O(n² )	O(n² )	不稳定	O(1)	n 小时较好
选择	O(n² )	O(n² )	不稳定	O(1)	n 小时较好
插入	O(n² )	O(n² )	稳定	O(1)	大部分已排序时较好
基数	O(log_R B)	O(log_R B)	稳定	O(n)	B 是真数 (0-9) ， R 是基数 ( 个十百 )
Shell	O(nlogn)	O(n^s ) 1<s<2	不稳定	O(1)	s 是所选分组
快速	O(nlogn)	O(n² )	不稳定	O(nlogn)	n 大时较好
归并	O(nlogn)	O(nlogn)	稳定	O(1)	n 大时较好
堆	O(nlogn)	O(nlogn)	不稳定	O(1)	n 大时较好

冒泡排序

//冒泡排序
void bubble_sort(int *array, int length)
{
    int i, j, temp;
    for(i = 1; i < length; i++){
        for(j = length-1; j >= i; j--){
            if(array[j-1] > array[j]){
                exchange(array[j-1], array[j]);
            }
        }
    }
    return;
}

选择排序

//选择排序
void select_sort(int *array, int length)
{
    int i, j;
    int t, change, m;
    for(i = 0; i < length-1; i++){
        t = array[i];
        change = 0;
        for(j = i+1; j < length; j++){
            if(array[j] < t){
                t = array[j];
                m = j;
                change = 1;
            }
        }
        if(change){
            array[m] = array[i];
            array[i] = t;
        }
    }
    return;
}

插入排序

//插入排序
void insert_sort(int *array, int length)
{
    int i, j;
    int key;
    for(j = 1; j < length; j++){
        key = array[j];
        //将array[j]插入特定位置
        i = j-1;
        while(i >= 0 && array[i] > key){
            array[i+1] = array[i];
            i--;
        }
        array[i+1] = key;
    } //end for j
    return;
}

希尔排序

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

//希尔排序
void shell_sort(int *a, int length)
{
    int i, j, gap, temp;
    gap = 0;
    while (gap * 3 + 1<=length)
    {
        gap=gap * 3 + 1;
    }
    while (gap > 0)
    {
        for ( i = gap; i < length; i++ )
        {
            j = i - gap;
            temp = a[i];
            while (( j >= 0 ) && ( a[j] > temp ))
            {
                    a[j + gap] = a[j];
                    j = j - gap;
             }
            a[j + gap] = temp;
        }
        gap = ( gap - 1 ) /3;
    }
    return;
}

快速排序

//快速排序
int partition(int *a, int p, int r)
{
    int i, j;
    int t;
    t = a[r];
    i = p-1;
    for(j = p; j < r; j++){
        if(a[j] <= t){
            i++;
            exchange(a[i], a[j]);
        }
    }
    exchange(a[i+1], a[r]);
    return i+1;
}

void quick_sort(int *a, int p, int r)
{
    int q;
    if(p < r){
        q = partition(a, p, r);
        quick_sort(a, p, q-1);
        quick_sort(a, q+1, r);
    }
    return;
}

归并排序

//归并排序
void merge(int *a, int p, int q, int r)
{
    int i, j, n1, n2, k;
    int *left, *right;
    n1 = q - p + 1;
    n2 = r - q;
    left = new int[n1+1];
    right = new int[n2+1];
    for(i = 0; i < n1; i++){
        left[i] = a[p+i];
    }
    for(j = 0; j < n2; j++){
        right[j] = a[q+j+1];
    }
    left[n1] = inf;
    right[n2] = inf;
    i = 0;
    j = 0;
    for(k = p; k <= r; k++){
        if(left[i] <= right[j]){
            a[k] = left[i];
            i++;
        }
        else{
            a[k] = right[j];
            j++;
        }
    }
    return;
}

void merge_sort(int *a, int p, int r)
{
    int q;
    if(p < r){
        q = (p + r) / 2;
        merge_sort(a, p, q);
        merge_sort(a, q+1, r);
        merge(a, p, q, r);
    }
}