排序算法之交换类排序算法

刚看了交换类排序算法中的冒泡和快速排序，冒泡大家都很熟悉，但是又经常与简单选择排序搞混。快速排序

是目前工业级别，也就是公司当中最常用到的排序算法，这主要取决于它的高效。不多废话，首先贴出代码：

/*
 * Copyright (c) 2010-~ zhouyongfei
 *
 * The source code is released for free distribution under the terms of the GNU General Public License
 *
 *
 * Author: alen Chou
 * Created Time: 2010年07月19日 星期一 19时51分16秒
 * File Name: sort2.c
 * Description: 这个文件是我在复习交换类排序时写的一个文件。
 * 有冒泡排序，快速排序。
 *
 */

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0

/**
 *    
 * 冒泡排序的算法。
 * @:r[]为需要排序的数组
 * @:length为数组长度。
 * */
void BubbleSort(int r[],int length)
{
    int n = length;
    int i,j,x;
    int change;
    change = TRUE;
    /**
     * 外层循环控制的是已经有几个元素排好序
     * */
    for(i = 0;i < n&&change;++i){
        change = FALSE;
        /**
         * 这里的n-1-i就是当前要排序的最后一个元素的索引
         * 因为后面的以后排好序了
         * */
        for(j = 0;j < n-1-i;++j){
            if(r[j] > r[j+1]){
                x = r[j];
                r[j] = r[j+1];
                r[j+1] = x;
                change = TRUE;
            }
        }
    }

    printf("after sort:\n");
    for(i = 0;i < length;i++){
        printf("%d ",r[i]);
    }
    printf("\n");
}


/**
 * 一趟快速排序算法
 * @:r需要排序的数组
 * @:left当前指向的左端
 * @:right当前指向的右端
 * */

int QKPass(int r[],int left,int right)
{
    int x,low,high;
    x = r[left];
    low = left;
    high = right;
    while(low < high){
        while(low < high&&r[high] >= x){
            high--;
        }
        if(low < high){
            r[low] = r[high];
            low++;
        }

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

/**
 * 快速排序
 * @:r需要排序的数组
 * @:low需要排序部分的最左索引
 * @:high需要排序部分的最右索引
 * */
void QKSort(int r[],int low,int high)
{
    int pos;
    if(low < high){
        pos = QKPass(r,low,high);
        QKSort(r,low,pos-1);
        QKSort(r,pos+1,high);
    }
}


int main(int argc, char *argv[])
{
    
    int i;
    int arr[] = {48,62,35,77,55,14,35,98};
    //int arr[] = {48,62,35,77,53};

    int length = sizeof(arr)/sizeof(arr[0]);
    
    printf("before sort:\n");
    for(i = 0;i < length;i++){
        printf("%d ",arr[i]);
    }
    printf("\n");

    //BubbleSort(arr,length);

    QKSort(arr,0,length-1);

    printf("after sort:\n");
    for(i = 0;i < length;i++){
        printf("%d ",arr[i]);
    }
    printf("\n");

    return 0;
}

首先，冒泡排序：算法中有两层循环。外层的控制需要对多少个元素进行排序（也即是将已经淀底的元素不用

再进行排序，由于冒泡排序，外层循环进行一次，一定是当前排序的几个元素中的最"重"元素到了当前相对的

最后位置。），直到个数为0；内层循环就是不断的控制冒泡交换，将最重元素后移。这样就保证了，冒泡的正确性。

然后，快速排序：基于冒泡排序改进的一个算法，在一次快速排序过程中，将不相邻的元素进行冒泡交换，一

次快速排序结束后，会有一个终结的位置，因此利用这个终结的地方（再当前序列中，这个终结位置前面的所

有元素一定是小于这个位置后面的所有元素的。所以，保证了序列间的有序性）然后利用分治策略，将大的序

列分成小的序列，逐一进行快速排序。这样，效率会大大提高。

好了，这两个算法我的理解就基本这么多了，可能有些更重要的地方没有描述到，有兴趣的留言讨论，谢谢