經典算法學習——快速排序

經典算法學習——快速排序

快速排序應該算是在面試筆試中最常用的算法了，各位面試官都非常喜歡。排序效率在同為O(N*logN)的幾種排序方法中效率較高，因此經常被采用，其中的思想也是用了分治法和遞歸的思想。示例代碼上傳到：https://github.com/chenyufeng1991/QuickSort

算法的基本思想是：

（1）先從數列中取出一個數作為基准數（常常選第一個數）；

（2）分區過程，比這個數大的數放到它的右邊，小於或等於的數全放到它的左邊；

（3）再對左右區間重復第二步，直到每個區間只有一個數位置，即左邊界下標等於右邊界下標；

簡化描述為：

1.i= L, j=R,基准數即為a[i]，保存起來;

2.j--,由後向前找比它小的數，找到後將此數放到a[i]中；

3.i++,由前向後找比它大的數，找到後將此數填入到a[j]中；

4.遞歸執行2，3兩步，直到i==j，最後將基准數填入a[i]中；

具體代碼實現如下：

//
//  main.c
//  QuickSort
//
//  Created by chenyufeng on 16/1/27.
//  Copyright © 2016年 chenyufengweb. All rights reserved.
//

#include 

int *quickSort(int arr[],int l,int r);
void quickSort02(int *arr,int l,int r);

int main(int argc, const char * argv[]) {

    int numArr[5] = {3,6,0,9,4};

    //使用指針返回數組，返回的其實是數組的頭指針；
    /**
     *  使用返回指針；
     */

//    int *retArr;
//    retArr = quickSort(numArr, 0, 4);
//    for (int i = 0; i < 5; i++) {
//        //取數組值
//        printf("%d ",*(retArr + i));
//    }


    /**
     *  直接傳遞引用,比較方便；
     */
    quickSort02(numArr, 0, 4);
    for (int i = 0; i < 5; i++) {
        printf("%d ",numArr[i]);
    }
}

int *quickSort(int arr[],int l,int r){
    //當左右指針相等的時候直接返回；
    if (l < r) {
        //此時的x就是基准值；
        int i = l,j = r,x = arr[l];

        //下面的while循環表示一次分治，也就是進行一次排序；
        while (i < j) {
            //先從基准值右側找出小於基准的值；
            while (i < j && arr[j] >= x) {
                j--;
            }
            if (i < j) {
                //交換順序，i++；
                arr[i++] = arr[j];
            }

            //從基准值左側找出大於基准的值；
            while (i < j && arr[i] < x) {
                i++;
            }
            if (i < j) {
                //交換順序，j--;
                arr[j--] = arr[i];
            }
        }
        //把基准值放入arr[i]位置；
        arr[i] = x;
        //遞歸，左右兩側分別進行快排；
        quickSort(arr, l, i - 1);
        quickSort(arr, i + 1, r);
    }
    return arr;
}

void quickSort02(int *arr,int l,int r){
    //當左右指針相等的時候直接返回；
    if (l < r) {
        //此時的x就是基准值；
        int i = l,j = r,x = arr[l];

        //下面的while循環表示一次分治，也就是進行一次排序；
        while (i < j) {
            //先從基准值右側找出小於基准的值；
            while (i < j && arr[j] >= x) {
                j--;
            }
            if (i < j) {
                //交換順序，i++；
                arr[i++] = arr[j];
            }

            //從基准值左側找出大於基准的值；
            while (i < j && arr[i] < x) {
                i++;
            }
            if (i < j) {
                //交換順序，j--;
                arr[j--] = arr[i];
            }
        }
        //把基准值放入arr[i]位置；
        arr[i] = x;
        //遞歸，左右兩側分別進行快排；
        quickSort(arr, l, i - 1);
        quickSort(arr, i + 1, r);
    }
}