排序算法复习——交换类排序

在交换类排序算法中，有冒泡排序和快速排序。

冒泡排序：

这个算法大家估计很熟悉了，不做介绍了。

这里有一个算法优化的地方，那就是设置标志位，如果在上一趟的比较当中，没有进行交换的话，就说明已经排好序了，不需要再进行排序了。

演练程序：

#include <stdio.h>

#define N 10

int main()
{
    int a[N] = {62, 48, 35, 77, 55, 14, 35, 98, 22, 10};
    int tmp, i, j, flag;

    for(i = 0; i < N; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");

    flag = 1;
    /*控制比较的趟数，总共比较N-1趟*/
    for(i=0; i < N-1 && flag==1; i++) {
        flag = 0;
        /*相邻的两个元素进行比较，把泡泡冒到最底*/
        for(j=0; j < N-i-1; j++) {
            if(a[j] > a[j+1]) {
                tmp = a[j+1];
                a[j+1] = a[j];
                a[j] = tmp;
                flag = 1;
            }
        }
    }

    for(i = 0; i < N; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

执行结果：

62 48 35 77 55 14 35 98 22 10
10 14 22 35 35 48 55 62 77 98

快速排序：

对于快速排序，一般是这么来设计的：首先保存第一个元素到一个变量x中，让它当作一个枢纽值，然后设置low和high下标分别指向最低处和最高处，总之，在一趟排序之后，x所放的位置要保证x前面的元素比x都小，x之后的元素都比x大就行了。

演练程序：

#include <stdio.h>

#define N 10

int sort(int *a, int low, int high)
{
    int pos, x;

    x = a[low];
    while(low < high) {
        while(low<high && a[high] >= x) {
            high--;
        }
        if(low < high) {
            a[low] = a[high];
            low++;
        }
        while(low<high && a[low] <= x) {
            low++;
        }
        if(low < high) {
            a[high] = a[low];
            high--;
        }
    }
    a[low] = x;
    pos = low;
    return pos;
}

void quicksort(int *a, int low, int high)
{
    int pos;

    if(low < high) {
        pos = sort(a, low, high);
        quicksort(a, low, pos-1);
        quicksort(a, pos+1, high);
    }
}

int main()
{
    int a[N] = {62, 48, 35, 77, 55, 14, 35, 98, 22, 10};
    int i, j;

    for(i = 0; i < N; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");

    quicksort(a, 0, N-1);

    for(i = 0; i < N; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

执行结果：

62 48 35 77 55 14 35 98 22 10
10 14 22 35 35 48 55 62 77 98