排序算法-快速排序

有时候发现越写代码越麻木了,很多代码都copy,不深究。难道就这样甘愿当一辈子码农。

NO

所以最近又拾起了看书的习惯了,先看看算法吧。

冒泡那些就不说了。这里主要描述一下快速排序。

快速排序简单说就是选一个基数作比较,小的在左边,大的在右边。然后两边在按照相同的办法进行排序。

这是一种分治法,大事化小,小事再化小。当最后分解为三个数/两个数的时候,左右一分就排序完成了。

对于递归的算法,最重要的就是需要找到每个部分的相同点。就比如快速排序,相同的地方就是,每部分都要选择基数,然后按照基数左右排序。

下面附上代码:

public static void sort(int[] data, int left, int right) {
    if(left > right)
        return;
    int tmp = data[left];                // 选择最左边数作为基数
    int l = left, r = right;             // 两边的下标
    while(l < r) {                       // 替换一轮:先替换左边,再替换右边(如果你选择最右边为基数,可以先替换右边再替换左边)
        while(l < r && tmp < data[r])    // 从右边找小于基数的下标
            r--;
        if(l < r) {
            data[l] = data[r];           // 替换左边
            l++;                         // 肯定小于基数了,所以下标移动一下,可以尝试去掉结果一样
        }
        while(l < r && tmp > data[l])    // 从左边找大于基数的下标
            l++;
        if(l < r) {
            data[r] = data[l];           // 替换右边
            r--;                         // 肯定大于基数了,所以下标移动一下,可以尝试去掉结果一样
        }
    }
    data[l] = tmp;                       // 基数
 
    // 分别排序两边
    sort(data, left, l - 1);             // 排序左边
    sort(data, l + 1, right);            // 排序右边
}

参考文章:http://blog.csdn.net/morewindows/article/details/6684558