学步园

快速排序是一类基于“交换”进行的排序方法，其中最简单的排序的方法是起泡排序，也说冒泡排序。这是我最初学会的排序算法，算是入门级的算法吧。

起泡算法：

思想：每进行一次起泡会把最大的元素交换到最后，进行n-1次就是按关键字排好序的序列。

代码：

void bubble_sort(int *arr,int n) {
    for(int i = 0; i < n; i ++) {
        for(int j = 1; j < n - i; j ++){
            if(arr[j] < arr [j - 1])
            swap(arr[j] ,arr[j - 1]);
        }
    }
}

有一个比较比较快速的跳出循环的条件。如果，在趟的起泡排序的过程中没有进行交换，那么说明，序列已经是有序的了，可以跳出了。

void bubble_sort(int *arr,int n) {
    for(int i = 0; i < n; i ++) {
        bool  flag = false;
        for(int j = 1; j < n - i; j ++){
            if(arr[j] < arr [j - 1]){
                swap(arr[j] ,arr[j - 1]);
                flag = true;
            }
        }
        if( ! flag ) break;
    }
}

分析：起泡排序的平均时间复杂度为O(n^2)的。

快速排序：

快速排序是对起泡排序的一种改进。

思想：它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可对这两部分继续进行排序，已达到整个序列有序。该过程是基于分治的思想。

具体做法：

1.选择一个枢轴，作为key。

2.把小于key的放在key左边，把大于key的放在key右边。

3.对左右区间上的关键字在进行第二步。

分区代码：

int once_quick_sort(int *arr,int l,int r) {
    int key = arr[l];
    while(l < r){
        while(l < r && arr[r] > key) --r;//why >=?
        arr[l] = arr[r];
        while(l < r && arr[l] < key) ++l;
        arr[r] = arr[l];
        printf("%d %d\n",l,r);
    }
    arr[l] = key;
    return l;
}

主代码区：

void quicksort(int *arr,int l,int r){
    if(l < r) {
        int p = once_quick_sort(arr, l, r);
        quicksort(arr, l, p-1);
        quicksort(arr, p+1, r);
    }
}

写到一起：

void quicksort(int *arr, int l, int r) {
    if(l < r) {
        int key = arr[l],low = l ,high = r;
        while(l < r) {
            while(l < r && arr[r] >= key) -- r;// >= means that small than key is l;
            arr[l] = arr[r];
            while(l < r && arr[l] < key) ++l;// <= means that
            arr[r]= arr[l];
        }
        arr[l] = key;
        o_quicksort(arr, low, l - 1);
        o_quicksort(arr, l + 1, high);
    }
}

分析：就平均时间而言，快速排序是目前被认为最好的一种内部排序方法。