NDK37.归并排序、快速排序。

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

稳定排序：排序后，值相同的元素，依旧保持原有的顺序。
eg: 冒泡排序、插入排序、选择。
不稳定排序：排序后，值相同的元素，顺序发生了改变。
eg: 希尔排序(分组排序时影响了)、

一般正常开发，要会用模板(泛型)template <class T>的方式，将对象进行排序处理。

template <class T>
void bubbleSort(T arr[], int len) {
    // ...
}   

2.mergeSort 归并排序(分治)：将两个有序数组，归并到一个数组中，并且要排序好。

思想：
原始数据：[1,2,23,87,22,13,17,12]
将数据分割成2组: [1,2,23,87]; [22,13,17,12]
再将数据分成2组: [1,2];[23,87]; [22,13];[17,12]
再讲数据分成2组: [1],[2];[23],[87]; [22],[13];[17],[12]
由于数据不能再分割，对两两数据进行归并排序。
[1,2],[23,87]; [13,22][12,17]
再往上进行两两归并排序，排序结果为:
[1,2,23,87]; [12,13,17,22]
对两组数据，进行最后一次归并排序, 完成归并排序：
[1,2,12,13,17,22,23,87]
使用递归、循环的思路来实现。

归并的思路：

拷贝数组，i指向前面数组的第一个元素，j指向后面数组的第一个元素；
i，j指向的元素进行比较，谁的元素小，存入新的数组中，并且对应的i,j指针后移。
再次将i,j指向的元素比较，谁的元素小，存入新数组。直到数组排序完成。

// 对数组区间[l,mid],[mid+1,r]进行归并
void merge_(int arr[],int l,int mid,int r) {
    // 1.对数组进行1次拷贝。
    int temp[r - l + 1]; // 闭区间所以要+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){ // 左边四个都挪过来了，只需要加J
            arr[k] = temp[j-l];
            j++;
        } else if(j > r){ // 右边的都挪过来了，只需要加I。
            arr[k] = temp[i-l];
            i++;
        } 
        // 临时数据里面的i位置，j位置比较。
        else if(temp[i-l] < temp[j-l]) { //比较左右的第一个元素。
            arr[k] = temp[i-l]; // 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; // 右移一位：相当于/2
    mergeSort_(arr, l, mid); // 递归调用左边分组
    mergeSort_(arr, mid+1, r); // 递归调用右边分组
    
    // 优化：已经接近排好序,不需要再归并。
    if(arr[mid] > arr[mid+1]){
        merge_(arr, l, mid, r); // 合并左右两个已排序的数组，成一个新数组。
    }
}
// 对arr数组进行归并排序
void mergeSort(int arr[], int len){
    mergeSort_(arr, 0, len-1);
}
void main() {
    // 归并排序。
    ArrayUtil::sort_array("mergeSort", mergeSort, arr, len);
}

时间复杂度求解

每一列还是O(N), 列数log₂N ，所以时间复杂度是O(NLog₂N)

3.quickSort快速排序(分治)

思想：选一个数做基准，小的放左边，大的放右边。不断递归直到只有一个元素或没有元素。
partition划分。

原数据: [1，4,6,8，2，-12,23]
1.选1为基准，小于1的都放在左边，大于1的都放在右边。此时1排好序了
[-12, 1, 4,6,8,2,23]
2.递归：对左边选-12快速进行快速排序, 右边选4为基准。此时4也排好序了
[-12,1,2, 4, 6,8,23]
3.再选2,6为基准，不断递归快排

原数据：[8,7,6,9,12,24,2]

1. 8作为基准值v，一块区域位置数据<v；另一块区域内容数据>v. i作为数组索引。
   中间分隔位置p(指向小数据区的最后元素)。
   如果数据>v,只需要i++位置后挪；
   如果数据<v,将数据与大数据区第一个位置交换swap(arr[p+1,arr[i])，然后p++，i++
2. 初始的时候，v，t指向同一个位置。i从非首元素开始。
   i指向数据 如果比t指向数据小，i,t交换

// 对区间进行分割操作, 大的放右边，小的放左边。
// 给p的元素排序。
int partition_(int arr[], int left, int right){
    //优化1:在区间[left,right]随机位置进行比较。跟随机位置的元素比较。
    //swap(arr[left], arr[rand()%(right-left+1) +left]);
    
    int v = arr[left]; // 第一个元素left做基准点。
    int p = left; // 以p为分割，[left+1,p]<v, [p+1,right]>v
    
    for(int i=left, i<=right; ++i) {
        if(arr[i] < v){
            // 只处理小于的情况。交换数据(与大区第一个元素arr[p+1]交换)
            swap(arr[p+1], arr[i]);
            p++; // 小于的里面多一个元素，分割位置后移。
        }   
    }
    swap(arr[left], arr[p]); //交换:v/小数据区最后一个元素。完成v的排序。
    return p; // 返回分割位置,便于递归。
}

// 对数组arr区间[l,r] 进行快速排序。
void quickSort_(int arr[], int left, int right){
    if(left > right) return; // 递归到底的情况
        
    int p = partition_(arr, left,right); //左右分割点，p已经排序了
    quickSort_(arr, left, p-1); //左部分遍历
    quickSort_(arr, p+1, right);//右部分遍历
}
// 快速排序
void quickSort(int arr[], int len){
    // srand(time(NULL)); // 初始化随机种子
    quickSort_(arr, 0, len-1);
}
ArrayUtil::sort_array("quickSort", quickSort,arr1,len);

已接近排好序的数组，退化成冒泡排序， 成时间复杂度O(n²)
此时使用merge排序，效果更好。
优化：取[l,r]中的随机元素，作为基准点。排序能快很多，单还是比归并排序慢一些。

public static void quickSort(int[] a) {
    if(a.length>0) {
        quickSort(a, 0 , a.length-1);
    }
}
 
private static void quickSort(int[] a, int low, int high) {
    //1,找到递归算法的出口
    if( low > high) {
        return;
    }
    //2, 存
    int i = low;
    int j = high;
    //3,key
    int key = a[ low ];
    //4，完成一趟排序
    while( i< j) {
        //4.1 ，从右往左找到第一个小于key的数
        while(i<j && a[j] > key){
            j--;
        }
        //4.2 从左往右找到第一个大于key的数
        while( i<j && a[i] <= key){
            i++;
        }
        //4.3 交换
        if(i<j) {
            int p = a[i];
            a[i] = a[j];
            a[j] = p;
        }
    }
    // 4.4，调整key的位置
    int p = a[i];
    a[i] = a[low];
    a[low] = p;
    //5, 对key左边的数快排
    quickSort(a, low, i-1 );
    //6, 对key右边的数快排
    quickSort(a, i+1, high);
}

三路快速排序。

大量重复数据，快速排序比较慢。系统里面的排序，三路快排比较多。

// 再优化：三路快速排序。分三块，一块内容<v,一块内容=v,一块内容>v.
// 递归对小于，大于部分进行三路快排。
lt: 指向小数据区的最后元素； [left+1, lt]
gt: 指向大数据区的第一个元素，从后往前+数据；[gt, right]
i: 指向中区数据最后一个元素， [lt+1, i)

void quickSort3Ways_(int arr[], int left, int right){
    if(left > right) return; // 递归到底的情况
    
    // swap(arr[left], arr[rand()%(right-left+1)+left]);
    int v = arr[left]; // 取left指针的元素，作为基准。
    
    int lt = left;    //[left+1, lt]   小于v的集合
    int gt = right+1; //[gt, right]    大于v的集合
    int i  = left+1;  //[lt+1, i)   中间等于v的集合。
    while(gt > i) { //循环终止条件。
        if(arr[i] > v) { //大于v
            swap(arr[i], arr[gt-1]); 
            gt--; // 指针前移
            // 从后面拿一个元素来换，由于这个元素没有排序，所以i保持不变。
            // 这个元素，后面还要再参加排序。
        } else if(arr[i] < v){ //小于v
            swap(arr[i], arr[lt+l]);
            lt++; // 小数据区+1
            i++;  // 中数据区尾指针后移
        } else {  // arr[i]==v
            i++;  // 中数据区+1 
        }
    }
    swap(arr[left], arr[lt]); //排序完,交换v和 小区的最后元素。完成v的排序。
    
    quickSort_(arr, left, lt-1); //左部分遍历
    quickSort_(arr, gt, right);  //右部分遍历
}
void quickSort3ways(int arr[], int len){
    srand(time(NULL)); 
    quickSort3Ways_(arr, 0, len-1);
}

不同场景，选择不同排序算法(随机，接近排序，大量重复)
随机的：快排、归并. 各种场景都适用。
接近有序的：插入排序。
大量重复的：三路快排。

二叉树：堆排序。