一、快速排序

1.挖坑法

1.过程

1.为了使用方便我们默认第一个数为key，key的值可以看作单独提出来了，key所在的(pivot)坑的位置

先从右边开始找比key小的数，找到后将值传给pivot所在位置，同时pivot指向右边
在这里插入图片描述
2.再从左边找比key大的数，找到后将值传给左边pivot所在位置，同时pivot指向左边
在这里插入图片描述
3.当begin与end指向同一个位置时，则将关键字传入进去，循环结束
在这里插入图片描述

2.对于递归结束条件的分析

在这里插入图片描述
当递归到最后时，发现只剩下一个数或者没有数存在，

而在循环中成立的条件为 lelftright时，没有数存在**

3. 代码实现

void swap(int* pa, int* pb)
{
    int tmp = 0;
    tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}
int getmid(int* a, int left, int right)//三数取中  为了防止有序时时间复杂度为O(N^2)
{
    int mid = (left + right) / 2;
    if (a[left] > a[mid])
    {
        if (a[right] > a[left])
        {
            return left;
        }
        else if (a[mid] > a[right])
        {
            return mid;
        }
        else
        {
            return right;
        }
    }
    else//a[left]  <a[mid]
    {
        if (a[right] < a[left])
        {
            return left;
        }
        else if (a[mid] < a[right])
        {
            return mid;
        }
        else
        {
            return right;
        }
    }
}
void   quicksort(int*a,int  left, int right )
{
    if (left >= right)//left==right时，只存在一个值，left>right时，区间不存在
    {
        return;
    }
    int index = getmid(a, left, right);
    swap(&a[left], &a[index]);//默认key的位置为左边第一个
    int begin = left;
    int end =  right;
    int pivot = begin;//pivot代表坑位
    int key = a[begin];
    while (begin < end)//一趟排序
    {
        while (a[end] >= key&&begin<end)//右边找小，放到左边
        {
            end--;
        }
        a[pivot] = a[end];//把小的放在左边的坑位中，自己形成新的坑位
        pivot = end;
        while (a[begin] <= key&&begin<end)//左边找大，放到右边
        {
            begin++;
        }
        a[pivot] = a[begin];//把大的放在右边的坑位中，自己形成新的坑位
        pivot = begin;
    }
    pivot = begin;//当begin==end时，循环结束，将关键字赋值给begin所在位置
    a[pivot] = key;//通过坑位分成两部分   [left    pivot-1] pivot [pivot+1   right]
    if (pivot - 1 - left > 10) //小区间优化
    {
        quicksort(a, left, pivot - 1);
    }
    else
    {
        insertsort(a + left, pivot - 1 - left+1);//随着递归的变化 ，左区间有可能不从0开始，右区间是下标变化要+1
    }
    if (right - (pivot + 1) > 10)
    {
        quicksort(a, pivot + 1, right);
    }
    else
    {
        insertsort(a + pivot+1, right - (pivot + 1)+1);
    }
}

4.快速排序的时间复杂度

理想情况下，每次都用坑pivot 将left与right区间平分即满二叉树
在这里插入图片描述每一层都会将所有数遍历一遍，所有每一层的时间复杂度为O(N)一共遍历了高度次根据二叉树性质：2^h-1=N h=log N 快速排序的整体时间复杂度为O(N*logN)

5.三数取中

快排什么时候为最坏情况

有序时最坏

以顺序为列，每次只能选出一个数此时的时间复杂度为O(N^2)
在这里插入图片描述所以为了防止这种情况的发生，采用三数取中

6.小区间优化

使用小区间优化是为了减少函数调用的次数
在这里插入图片描述当我们递归会发现最后几层的函数调用占据了绝大多数我们假设当 一个区间内相差不超过10，就消除消除的部分则使用直接插入排序直接插入排序在这里: 八大排序(上)

2.左右指针法

1.过程

简单来说，就是先从右面找比关键字小的，再从左边找比关键字大的，两者交换，

当left==right时，将此时的值与关键字交换
在这里插入图片描述

2.代码实现

void swap(int* pa, int* pb)
{
    int tmp = 0;
    tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}
int  partsort(int* a, int left, int right)//左右指针法
{
    if (left >= right)
    {
        return;
    }
    int begin = left;
    int end = right;
    int key = left;
    while (begin < end)
    {
        while (a[end] >= a[key] && begin < end)
        {
            end--;
        }
        while (a[begin] <= a[key] && begin < end)
        {
            begin++;
        }
        swap(&a[begin], &a[end]);//当左边找到小的 ，右边找到大的时候 就将两者值交换
    }
    swap(&a[key], &a[begin]);
    return begin;    // [left ,begin-1] begin [begin+1,  right]
}
int getmid(int* a, int left, int right)//三数取中  为了防止有序时时间复杂度为O(N^2)
{
    int mid = (left + right) / 2;
    if (a[left] > a[mid])
    {
        if (a[right] > a[left])
        {
            return left;
        }
        else if (a[mid] > a[right])
        {
            return mid;
        }
        else
        {
            return right;
        }
    }
    else//a[left]  <a[mid]
    {
        if (a[right] < a[left])
        {
            return left;
        }
        else if (a[mid] < a[right])
        {
            return mid;
        }
        else
        {
            return right;
        }
    }
}
void   quicksort(int* a, int  left, int right)
{
    int keyindex = partsort(a,left, right);
    if (keyindex - 1 - left > 10)
    {
        quicksort(a, left, keyindex - 1);
    }
    else
    {
        insertsort(a + left, keyindex - 1 - left + 1);//随着递归的变化 ，左区间有可能不从0开始，右区间是下标变化要+1
    }
    if (right - (keyindex + 1) > 10)
    {
        quicksort(a, keyindex + 1, right);
    }
    else
    {
        insertsort(a + keyindex + 1, right - (keyindex + 1) + 1);
    }
}

3.前后指针法

1.过程

1.当cur的值比key大时，cur++
在这里插入图片描述
2.当cur的值比key小时 ,prev++ ，并交换两者的值
在这里插入图片描述
3.当cur遍历完数组时，就将prev位置的值与key位置的值交换
在这里插入图片描述

2.代码实现

void swap(int* pa, int* pb)
{
    int tmp = 0;
    tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}
int getmid(int* a, int left, int right)//三数取中  为了防止有序时时间复杂度为O(N^2)
{
    int mid = (left + right) / 2;
    if (a[left] > a[mid])
    {
        if (a[right] > a[left])
        {
            return left;
        }
        else if (a[mid] > a[right])
        {
            return mid;
        }
        else
        {
            return right;
        }
    }
    else//a[left]  <a[mid]
    {
        if (a[right] < a[left])
        {
            return left;
        }
        else if (a[mid] < a[right])
        {
            return mid;
        }
        else
        {
            return right;
        }
    }
}
int partsort(int* a, int left, int right)//前后指针法
{
    if (left >= right)
    {
        return 0;
    }
    int key = left;
    int prev = left;
    int cur = left + 1;
    while (cur <= right)
    {
        if (a[cur] < a[key] && ++prev != cur)//如果cur位置值比key位置值小 ，prev++ 并交换两者值
        {                                //如果prev向后移后的值与key位置值相等就不进入循环 没有交换的必要
            prev++;
            swap(&a[prev], &a[cur]);
        }
        cur++;
    }
    swap(&a[prev], &a[key]);//当cur出了right范围，将prev位置值与key位置值交换
    return prev;
}
void   quicksort(int* a, int  left, int right)
{
    int keyindex = partsort(a,left, right);
    if (keyindex - 1 - left > 10)
    {
        quicksort(a, left, keyindex - 1);
    }
    else
    {
        insertsort(a + left, keyindex - 1 - left + 1);//随着递归的变化 ，左区间有可能不从0开始，右区间是下标变化要+1
    }
    if (right - (keyindex + 1) > 10)
    {
        quicksort(a, keyindex + 1, right);
    }
    else
    {
        insertsort(a + keyindex + 1, right - (keyindex + 1) + 1);
    }
}

4.非递归

非递归借助了数据结构栈的模拟:栈和队列的实现

1.过程
在这里插入图片描述 栈有先进后出的原则 ，所以我们先判断下是否符合区间值>1的条件，如果符合，则先将右边的右入栈，再入右边的左，其次入左边的右，再入，做左边的左 呈现出来则为，左边的左，右，右边的左，右
2.代码实现

int   partsort(int* a, int  left, int right)
{
    if (left >= right)
    {
        return 0;
    }
    int begin = left;
    int end = right;
    int pivot = begin;
    int key = a[begin];
    while (begin < end)
    {
        while (a[end] >= key && begin < end)
        {
            end--;
        }
        a[pivot] = a[end];
        pivot = end;
        while (a[begin] <= key && begin < end)
        {
            begin++;
        }
        a[pivot] = a[begin];//把大的放在右边的坑位中，自己形成新的坑位
        pivot = begin;
    }
    pivot = begin;//当begin==end时，循环结束，将关键字赋值给begin所在位置
    a[pivot] = key;//通过坑位分成两部分   [left    pivot-1] pivot [pivot+1   right]
    return pivot;
}
void quicksortNonR(int* a, int n)
{
    ST st;
    stackinit(&st);
    stackpush(&st, n - 1);//先将右 输入  再将左输入
    stackpush(&st, 0);//输出时，则为左先输出 ，右再输出
    while (!stackempty(&st))
    {
        int left = stacktop(&st);
        stackpop(&st);
        int right = stacktop(&st);
        stackpop(&st);
        int keyindex = partsort(a, left, right);// [left    keyindex-1] keyindex [keyindex+1   right]
        if (keyindex + 1 < right)//栈符合先进后出的原则 
        {
            stackpush(&st, right);//先入右区间的右 再入右区间的左
            stackpush(&st, keyindex + 1);//输出右区间的左 再输出右
        }
        if (left < keyindex - 1)//再入左区间的右  左区间的左
        {
            stackpush(&st, keyindex - 1);//输出左区间的左，再输出右
            stackpush(&st, left);
        }
    }
    stackdestroy(&st);
}

二、归并排序

1.递归

1.过程

在这里插入图片描述
通过递归的方式使左半区间与右半区间有序，最后使整体区间有序

2.代码实现

void mergesort(int* a, int left, int right, int* tmp)//
{
    if (left >= right)//当区间不存在或者只有一个时 返回
    {
        return;
    }
    int mid = (left + right) / 2;
    mergesort(a, left, mid, tmp);//左半区间
    mergesort(a, mid+1, right, tmp);//右半区间
    int begin1 = left;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = right;
    int index = left;
    while (begin1 <= end1 && begin2 <= end2)//将小的的依次放入新的临时数组中
    {
        if (a[begin1] < a[begin2])
        {
            tmp[index] = a[begin1];
            index++;
            begin1++;
        }
        else
        {
            tmp[index] = a[begin2];
            index++;
            begin2++;
        }
    }
    while (begin1 <= end1)//如果此时的左区间未完全排完 则进入循环
    {
        tmp[index] = a[begin1];
        index++;
        begin1++;
    }
    while (begin2 <= end2)//如果此时的右区间未完全排完 则进入循环
    {
        tmp[index] = a[begin2];
        index++;
        begin2++;
    }
    int i = 0;
    for (i = 0; i <=right; i++)//将此时排好的临时数组传回原数组中
    {
        a[i] = tmp[i];
    }
}
void sort(int* a, int n)//归并排序  递归
{
    int left = 0;
    int right = n - 1;
    int* tmp = (int*)malloc(sizeof(int) * n);
    mergesort(a, left, right, tmp);
    free(tmp);
}

3.归并排序的时间复杂度

在这里插入图片描述
每次都分为两个对半的区间

可以看作是一个满二叉树

2^h-1=N h=log N

当向上递归排序时,每一层的区间排序会遍历到所有数 n

时间复杂度为O(N)

即归并排序整体时间复杂度为O(N*log N)

4.递归的缺陷

如果栈深度太深，栈的空间不够用，可能会造成溢出

在这里插入图片描述

2.非递归

1.过程

采用循环，从之前的底层开始进行，一直到整体有序结束

假设此时数组中有8个数

通过 [i ，i+gap-1] [i+gap ， i+2*gap-1] 每次都分为两个区间

则gap为1时就将左边区间个数为1 与右边区间个数为1 进行排序

gap为2时就将左边区间个数为2 与右边区间个数为2 进行排序

gap为4时就将左边区间个数为4 与右边区间个数为4 进行排序
在这里插入图片描述

2.代码实现

void mergesortNonR(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    int gap = 1;
    int i = 0;
    while (gap < n)
    {
        for (i = 0; i < n; i += 2 * gap)//以gap为间隔 分为 1   2   4
        {
            int begin1 = i;//[i  i+gap-1] [i+gap   i+2*gap-1]
            int end1 = i + gap - 1;
            int begin2 = i + gap;
            int end2 = i + 2 * gap - 1;
            int index = i;
            if (begin2 >= n)//右区间可能不存在
            {
                break;
            }
            if (end2 >= n)//右区间算多了,修正下
            {
                end2 = n - 1;
            }
            while (begin1 <= end1 && begin2 <= end2)//排序
            {
                if (a[begin1] < a[begin2])
                {
                    tmp[index] = a[begin1];
                    index++;
                    begin1++;
                }
                else
                {
                    tmp[index] = a[begin2];
                    index++;
                    begin2++;
                }
            }
            while (begin1 <= end1)
            {
                tmp[index] = a[begin1];
                index++;
                begin1++;
            }
            while (begin2 <= end2)
            {
                tmp[index] = a[begin2];
                index++;
                begin2++;
            }
            int j = 0;
            for (j = i; j <=end2; j++)
            {
                a[j] = tmp[j];
            }
        }
        gap *= 2;
    }
    free(tmp);
}

3.注意事项

在这里插入图片描述 左区间存在，右区间不存在时，左区间不需要归并

在这里插入图片描述

当将左区间的4个数，与右区间进行归并时发现右区间只有三个数，第4个数不存在，所以修正回第三个数作为end2

当左区间的数不够gap所分的数，右区间不存在时，若将左区间拷贝回去会出现随机值

所以进行归并的才拷贝回去，没有进行的就不需要拷贝 ,所以将返回过程放入循环中
在这里插入图片描述

三、计数排序

1.思想

1.统计数，与其下标的大小对应，观察每个下标所对应的数量，直接输出就排好序了，此时为绝对映射位置
在这里插入图片描述
2.若数字过大，前面的空间就会浪费掉，所以避免这种情况的发生，则进行相对位置的映射
在这里插入图片描述

2.代码实现

时间复杂度为O(N)

void countsort(int* a, int n)
{
    int i = 0;
    int j = 0;
    int max = a[0];
    int min = a[0];
    for (i = 0; i < n; i++)
    {
        if (max < a[i])
        {
            max = a[i];
        }
        if (min > a[i])
        {
            min = a[i];
        }
    }
    int range = max - min+1;//从0开始 所以多了一个数    
    int* count = (int*)malloc(sizeof(int) * range);
    memset(count, 0, sizeof(int) * range);//将count都初始化为0
    for (i = 0; i < n; i++)//统计次数
    {
        count[a[i] - min]++;//a[i]-min为相对映射位置
    }
    for (i = 0; i < range; i++)//遍历 下标范围
    {
        while (count[i]--)//判断每个下标中的次数
        {
            a[j] = i+min;
            j++;
        }
    }
    free(count);
}

八大排序(下)

一、快速排序

1.挖坑法

1.过程

2.对于递归结束条件的分析

3. 代码实现

4.快速排序的时间复杂度

5.三数取中

6.小区间优化

2.左右指针法

1.过程

2.代码实现

3.前后指针法

1.过程

2.代码实现

4.非递归

1.过程

2.代码实现

二、归并排序

1.递归

1.过程

2.代码实现

3.归并排序的时间复杂度

4.递归的缺陷

2.非递归

1.过程

2.代码实现

3.注意事项

三、计数排序

1.思想

2.代码实现

热门文章

最新文章

相关电子书