演算法【快速排序】

演算法【快速排序】

快速排序。選擇一個作為比較的元素，這裡我們選擇首元素，這個元素我叫他‘比較元素’；前後兩個指針（其實是索引變數）同時往後和往前進行遍歷，開頭的指針遇到比‘比較元素’大的元素停下來（空迴圈體的迴圈即可實現），末尾的指針往前遍歷，遇到比‘比較元素’小的元素停下來；兩個元素都停止後，交換兩個元素，交換後通過外面的大迴圈繼續讓指針運動起來；當兩個指針相遇或交錯時，退出大迴圈；之後將從後面跑來的指針的元素與‘比較元素（首元素）’交換（因為這時這個從後面跑來的指針一定指向小於或等於首元素的元素），這樣可以保證後面跑來的這個指針的位置元素，前面都是小於它的元素，後面都是大於它的元素；之後前面的進行遞歸，後面的也進行遞歸，遞歸的出口是開始的指針大於等於結束的指針（這個開始和結束的指針是上一個大的部分傳來的）。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 10

/**
 *  快排
*/

void quick_sort(int *arr, int size);
void recursion(int *arr, int start, int end);

// 快排
void quick_sort(int *arr, int size){
    recursion(arr, 0, size-1);
}


// 快排的遞歸邏輯
void recursion(int *arr, int start, int end){

    // 第一個作為比較的元素
    int comElement = arr[start];
    // 後面首元素的下標和尾元素的下標都要改變，現在先記錄一下。
    int start_temp = start;
    int end_temp = end;

    if(start_temp <= end_temp){
        while(1){
        // 移動前後兩個下標
        while(start<=end_temp && comElement > arr[++start]);    // 前下標沒有移動到最後且該位置元素大於比較元素時持續後移。即前下標超過末尾或元素大於等於比較元素時停止後移
        while(end >=start_temp && comElement < arr[end--]);     // 後元素小於起始元素 或 該位置元素小於等於比較元素時停止後移
        end++;      // 將最後往前移多的下標加上。

        if(start >= end) break;     // 後位置大於前位置，不進行交換

        // 這裡不能使用異或 或者 相加 的方式交換， 因為可能操作的是同一個元素。
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
        }

        int temp = arr[start_temp];
        arr[start_temp] = arr[end];
        arr[end] = temp;

        static int x_20231217 = 1;
        printf("第%d趟排序結果為：\t", x_20231217++);
        for(int i = 0; i<N; i++) printf("%d\t", arr[i]);
        printf("\n");

        // 遞歸
        recursion(arr, start_temp,end-1);   // end 的位置是之前 比較元素 的那個位置
        recursion(arr, end+1, end_temp);
	}

    
}


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

    // 生成隨機種子
    srand(time(0));

    int arr[N];
    for(int i = 0; i<N; i++) arr[i] = rand()%10 + 1;

    printf("原始數據為：\t\t");
    // 列印原始數據
    for(int i = 0; i<N; i++) printf("%d\t", arr[i]);
    printf("\n");

    // 調用快速排序
    quick_sort(arr, N);

    printf("最終數據為：\t\t");
    // 列印排序後的數據
    for(int i = 0; i<N; i++) printf("%d\t", arr[i]);
    printf("\n");

    getchar();
    return 0;
}