【数据结构】选择排序与快速排序（不稳定排序）

1.选择排序

步骤：

1. 将数组分为『已排序区』和『待排序区』
2. 每一轮从『待排序区』中选择一个最小的元素放在『已排序区』的尾部
3. 直到『待排序区』没有元素为止

过程：

1. 第一轮：3 10交换
2. 第二轮：9 4交换
3. 第三轮：8 5交换 以此类推

时间复杂度：O(n²)

选择排序是不稳定排序：53521 第一次51交换 第一个5就在第二个5后边了

2.快速排序

步骤：

1. l为左指针指向最左元素，r为右指针指向最右元素，同时选取l的值为基准值
2. 指针前移r–，找到第一个比基准值小的元素，放在l指针的位置
3. 指针后移l++，找到第一个比基准值大的元素，放在r指针位置
4. 重复2-3步，直到l与r重合，重合的位置即为基准值所在的位置
5. 这样，序列就分为了m n 两部分，前面的数值都小于基准值，后面的数值都大于等于基准值
6. 分别对两部分进行1-5步骤，递归，直至最终排序完成

时间复杂度:O(nlogn),不稳定，当序列完全逆序时，每次序列不能分成两部分了，时间复杂度退化为O(n²)

快速排序也是不稳定排序

3.代码演示

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
//宏  两数交换位置
#define swap(a, b){\
    __typeof(a) __temp = a;\
    a = b, b = __temp;\
}
//选择排序
void select_sort(int *num, int n){
    for(int i = 0; i < n; i++){
        for(int j = i + 1; j < n; j++){
            if(num[i] > num[j]) swap(num[i], num[j]);
        }
    }
    return ;
}
//快速排序
void quick_sort(int *num, int l, int r){
    if(r < l) return ;
    int x = l, y = r, z = num[l];
    while(x < y){
        while(x < y && num[y] >= z) y--;
        if(x < y) num[x++] = num[y];
        while(x < y && num[x] <= z) x++;
        if(x < y) num[y--] = num[x];
    }
    num[x] = z;
    quick_sort(num, l, x - 1);
    quick_sort(num, x + 1, r);
}

int main(){
    int num1[10] = {1, 2, 5, 3, 6, 7, 9, 8, 4, 10};
    int num2[10] = {1, 2, 5, 3, 6, 7, 9, 8, 4, 10};
    select_sort(num1, 10);
    quick_sort(num2, 0, 9);
    for(int i = 0; i < 10; i++){
        printf("%d ", num1[i]);
    }
    printf("\n");
    for(int i = 0; i < 10; i++){
        printf("%d ", num2[i]);
    }
    printf("\n");
    return 0;
}