数据结构算法之归并排序和快速排序

归并排序

归并排序.gif

可能图片不够清楚，可以看下这张图片

归并排序.jpg

实际就是不断分割然后排序再归并的过程

合并的过程其实看最后一步就可以了

image.png

首先：我们定义一个拷贝数组temp，把数据拷贝进去，然后将temp数据从中间隔开分为左边下标i和右边下下标j，拿左边第一个数据和右边第一个数据进行比较，小的放到arr的对应下标中，然后拿左边第二个数据和右边第二个数据进行比较，小的放到arr数组中，依次轮推。

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++;
        }
            // 临时数据里面的 i 位置和 j 位置去比较
        else if (temp[i - l] < temp[j - l]) {
            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);
}

时间复杂度：每一次合并的时候实际执行了n次，因为就一个for循环，如上图归并排序这图，实际拆分了几层就会执行几次合并，所以n个数据实际可以分为log2n层，所以时间复杂度是n*log2n

快速排序

1、先从数列中取出一个数作为基准数
2、分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边
3、再对左右区间重复第二步，直到各区间只有一个数

快速排序.gif

分析:
比如假设我们有一组数据 4 3 2 1 6 8 7
第一次的时候我们想要的结果是 3 2 1 4 6 8 7

image.png

image.png

v代表我们基准数，arr[i+1]到arr[j]代表<v这个数，arr[j+1]到arr[i-1]代表>v的数,而e代表我们要查询的数
如果e>v那么很简单，就直接放在i的后面，i++就可以了，那如果比v小怎么办，其实也很简单,让当前元素与<v也就是j的下个位置j+1的数进行交换就可以了,最后的时候，我们的v元素和j这个位置进行交换，那么就能实现我们上面举例的结果，接下来，左边进行快速排序，右边也进行快速排序就可以了

看代码:

int partition(int arr[], int l, int r){
    // 优化，跟区间[l,r]随机位置进行比较
    swap(arr[l], arr[rand() % (r - l + 1) + l]);
    int v=arr[l];
    int p=l;
    for (int i = l; i <=r; ++i) {
        if(arr[i]<v){
            std::swap(arr[p+1],arr[i]);
            p++;
        }
    }
    std::swap(arr[l],arr[p]);
    return p;
}
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);
}

三路快速排序

image.png

我们设置基准数还是v，[i+1...lt]小于v，[lt + 1,i) = v，[gt,r] >v，e是我们查询的数
假设e==v，那么i++就可以了，如果，e>v那么就将e和gt-1的位置进行交换，并将gt进行自减，如果e<v那么就将e和it+1位置的数据进行交换，随后it和i++，直到i==gt循环结束，将v的数据和it位置的数据进行交换

代码如下

void quickSort3ways_(int arr[], int l, int r) {
    // 递归到底的情况
    if (l >= r) {
        return;
    }
    // 定义变量
    std::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) {//当gt与i重合的时候就表示便利完毕了
        if (arr[i] > v) {
            std::swap(arr[i], arr[gt - 1]);
            gt--;
        } else if (arr[i] < v) {
            std::swap(arr[i], arr[lt + 1]);
            i++;
            lt++;
        } else {
            i++;
        }
    }

    std::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);
}