数据结构和算法：05.稳定和不稳定排序、归并排序和快速排序、三路快排

具体代码请看：NDKPractice项目的datastructure

1. 稳定排序和不稳定排序：

稳定排序概念：通俗地讲就是能保证排序前两个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下，如果Ai = Aj，Ai原来在位置前，排序后Ai还是要在Aj位置前。

代表：

• 稳定排序：冒泡、插入、选择、归并
• 不稳定排序：希尔、快速排序、堆排序

2. 归并排序

每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。

时间复杂度：O(nlogn) 级别.

思想：

// 对数组区间 [l,mid] 和 [mid+1,r] 进行归并
void merge_(int arr[],int l,int mid,int r){
    // 1. 对数组进行一次拷贝
    int temp[r - l + 1];
    for(int i = l ;i <= r; ++i){
        temp[i -l] = arr[i];
    }
    // 2. 确定好分析之后的变量
    int i = l;
    int j = mid + 1;
    int k = l;
    for (; k <= r; ++k) {
        if(i > mid){
            arr[k] = temp[j - l];
            j++;
        }else if( j > r){
            arr[k] = temp[i -l];
            i++;
        }else if(temp[i - l] < temp[j - l]){ // 临时数据里面的 i 位置和 j 位置去比较
            arr[k] = temp[i - l];
            i++;
        } else{
            arr[k] = temp[j - l];
            j++;
        }
    }
}

// 对数组的 [l,r] 区间进行归并排序
void mergeSort_(int arr[], int l, int r){
    // 递归到底的情况
    if(l >= r)
        return;
    int mid = ( l + r) >> 1;
    mergeSort_(arr,l,mid);//左边归并排序，使得左子序列有序
    mergeSort_(arr,mid + 1,r);//右边归并排序，使得右子序列有序
    // 优化要根据具体的场景去做（因为前面是排好序的！！）
    if(arr[mid] > arr[mid + 1]){
        merge_(arr, l, mid, r);//将两个有序子数组合并操作
    }
}

// 归并排序
void mergeSort(int arr[],int len){
    mergeSort_(arr,0,len - 1);
}

2. 快速排序

思想：<v , >v

// 对数组 arr 区间[l,r] 进行分割操作
int partition_(int arr[], int l, int r) {// 10 , 20
    // 优化，跟区间[l,r]随机位置进行比较
    swap(arr[l], arr[rand() % (r - l + 1) + l]);
    int v = arr[l];
    // 以 p 为分割，[l+1,p]<v 和  [p+1,r] > v
    int p = l;
    for (int i = l; i <= r; ++i) {
        if (arr[i] < v) {
            // 只需要处理小于的情况
            swap(arr[p + 1], arr[i]);
            p++;
        }
    }
    swap(arr[l], arr[p]);
    return p;
}

// 对数组 arr 区间[l,r] 进行快速排序
void quickSort_(int arr[], int l, int r) {
    // 递归到底的情况
    if (l >= r) {
        return;
    }
    int p = partition_(arr, l, r);
    quickSort_(arr, l, p - 1); // 对基准元素左边的元素进行递归排序
    quickSort_(arr, p + 1, r); // 对基准元素右边的进行递归排序
}

// 快速排序
void quickSort(int arr[], int len) {
    srand(time(NULL)); // 初始化随机数发生器
    quickSort_(arr, 0, len - 1);
}

3. 三路快排

思想：分成 3块区域， <v , =v, >v

void quickSort3ways_(int arr[], int l, int r) {
    // 递归到底的情况
    if (l >= r) {
        return;
    }

    // 定义变量
    swap(arr[l], arr[rand() % (r - l + 1) + l]);
    int v = arr[l];

    int lt = l;//[l+1, lt] < v
    int gt = r + 1;// [gt,r] >v
    int i = l + 1;// [lt + 1,i) = v

    while (gt > i) {
        if (arr[i] > v) {
            swap(arr[i], arr[gt - 1]);
            gt--;
        } else if (arr[i] < v) {
            swap(arr[i], arr[lt + 1]);
            i++;
            lt++;
        } else {
            i++;
        }
    }

    swap(arr[l], arr[lt]);
    quickSort3ways_(arr, l, lt - 1);
    quickSort3ways_(arr, gt, r);
}

void quickSort3ways(int arr[], int len) {
    srand(time(NULL)); // 初始化随机数发生器
    quickSort3ways_(arr, 0, len - 1);
}