基本排序算法总结

排序算法的评价

评价排序算法的一般准则是：
▶ 平均情况下的排序速度
▶ 最优最劣情况下的速度
▶ 行为是否自然
▶ 是否以相等的关键字重排元素

数组的排序速度直接与比较（comparison）次数和交换（exchange）次数相关，其中交换的作用更大，因为占用的时间多。
如果频繁遭遇到最优最劣情况，则最优和最劣情况下的运行时间是重要的。
所谓自然（natural）行为的排序应该是，对已排序的表操作最容易，对失序越重的表操作越困难。
通常，如果有相等关键字的元素在排序前后，之间的相对位置并不改变，我们称之为该排序是稳定的。




气泡排序（bubble sort）
      
最著名（也最声名狼藉）的排序是气泡排序。

void bubble_sort(char *items, int count)
{
    int i, j;
    char t;
   
    for(i = 1; i < count; i++)
    {
        for(j = count-1; j >= i; j--)
        {
            if(items[j-1] > items[j])
            {
                t = items[j-1];
                items[j-1] = items[j];
                items[j] = t;
            }
        }
    }
}

分析：
两个 for 循环重复了比较的次数，所以比较的次数是恒定的：1 / 2(n平方 - n)
其中，外部循环执行 n - 1 次，内部循环执行 n/2 次，两式相乘得到以上公式。
下面是气泡排序的动画演示：

气泡排序动画演示


选择排序（selection sort）

选择排序中，先选择最小的元素并将其与第一个元素进行交换。然后剩余的 n - 1 个元素中选择最小值者并与第二个元素交换等，如此直到最后两个元素。

void select_sort(char *items, int count)
{
    int i, j, k;
    int exchange;
    char t;

    for(i = 0; i < count -1; i++)
    {
        exchange = 0;
        t = items[i];
        k = i;

        for(j = i+1; j < count; j++)
        {
            if(items[j] < t)
            {
                t = items[j];
                k = j;
                exchange = 1;
            }
        }

        if(exchange)
        {
            items[k] = items[i];
            items[i] = t;
        }
    }
}


分析：
和气泡算法一样，选择排序需要进行的比较次数同样为 1/2 (n平方 - n) 。尽管如此，但在平均情况下，选择排序的交换次数要少得多。
下面是选择排序的动画演示：

选择排序动画演示


插入排序（Insertion sort）

插入排序中，先对前两个元素进行排序，然后把第三个元素按序插入到已排好序的前两个元素中。随后是第四个插入到已排好序的前三个元素中，以此类推，直到所有元素都有序为止。

void insert_sort(char *items, int count)
{
    int i, j;
    char t;
   
    for(i = 1; i < count; i++)
    {
        t = items[i];
        j = i - 1;

        while(j >= 0 && items[j] > t)
        {
            items[j+1] = items[j];
            j--;
        }

        items[j+1] = t;
    }
}


分析：
与气泡排序和选择排序不同的是，插入排序的比较次数与被排表的初始排列有关。如果表是完全有序的，比较 n - 1 次，否则按 n 平方次进行。

因此，最劣情况下，与 气泡排序和选择排序一样差，平均情况稍好一点。然而这种办法的确有两个优点：
1. 排序是自然的，即表已排序时工作量最少，反序时工作量最大。这样，对基本已排序的表操作时，插入排序是最理想的。
2. 排序是稳定的，即相同关键字元素的相对位置，排序前后保持不变。

下面是插入排序的动画演示：

插入排序动画演示


前面几个算法，执行时间都是 n 平方级的，对于大量数据而言，排序速度非常慢，有时会完全不实用。
下面是两个较快的算法


希尔排序（Shell sort）

希尔排序是根据其发明者的名字（D.L.Shell）命名的。其一般方法是从插入排序导出并基于增量减少 （diminishing increments）。例如，首先，对间隔三个位置的元素排序；然后，再对间隔两个位置的元素排序；最后，对相邻元素进行排序。

排序的每一遍涉及相对较少的元素或已恰当排序的元素。因此，希尔排序是高效的，每一遍都提高了有序性。
增量的准确序列可以变化，唯一规则是最后增量必须为 1 。例如：9 ，5， 3， 2， 1 。以 2 的幂为增量值的序列是不可取的，出于复杂的数学原理，这种序列降低了排序算法的效率。

void shell_sort(char *items, int count)
{
    int i, j, k, gap;
    int gaps[5];
    char t;

    gaps[0] = 9; gaps[1] = 5; gaps[2] = 3; gaps[3] = 2; gaps[4] = 1;

    for(k = 0; k < 5; k++)
    {
        gap = gaps[k];
       
        for(i = gap; i < count; i++)
        {
            t = items[i];
            j = i - gap;

            while(j >= 0 && items[j] > t)
            {
                items[j+gap] = items[j];
                j = j - gap;
            }

            items[j+gap] = t;
        }
    }
}

分析：
希尔排序的执行与 n 的1.2 次方 成比例，相对于 n 平方排序而言，这是重大改进。
下面是希尔排序动画演示：

希尔排序动画演示


快速排序（quick sort）

快速排序是又 C.A.R.Hoare 发明的，一般被认为是目前最好的通用排序算法。快速排序基于交换排序，与同样基于交换排序的 气泡排序相比，其效果是惊人的。

快速排序的基本思想是分区（partition）。一般过程是先选一个比较数（comparand）的值，然后把数组分成两段。大于等于分区值的元素都放在一边，小于分区值的元素放在另一边。然后对数组的另一段重复上述过程，直到该数组完成排序。

排序的过程本质上递归的，而实际上，快速排序的最清晰实现就是递归算法。

选择比较数值的办法有两个，可以随机选取也可以选取数组中一组值求平均值得到。


void quick_sort(char *items, int count)
{
    qs(items, 0, count - 1);
}

void qs(char *items, int left, int right)
{
    int i, j;
    char x, t;

    i = left; j = right;
    x = items[(left+right)/2];

    do
    {
        while(items[i] < x && i < right)
            i++;
        while(x < items[j] && j > left)
            j--;

        if(i <= j)
        {
            t = items[i];
            items[i] = items[j];
            items[j] = t;
            i++; j--;
        }
    }while(i <= j);

    if(left < j)
        qs(items, left, j);
    if(i < right)
        qs(items, i, right);
}


分析：
快速排序的平均比较次数为 n log n ，近似交换次数 n/6 log n 。这两个数值远小于前面各种排序的相应参数。
需要注意的一个问题是，如果每个分区的比较数值选择了最大值，快速排序退化成 n 平方操作时间的排序。
快速排序是分而治之（divide and conqer）的策略，请参考另外一种采用 分治 策略的排序方法：归并排序（Merge Sort）（zz） 。
与归并排序不同的是， 最劣情况下，快速排序的的时间复杂度为 n 平方，而归并排序则是 nlogn 。

这里的这个算法写的不够清晰，请参看 寻找第k小的数 与 快速排序