八大排序 (下)

作者：lovevivi

2022-10-24
吉林
本文字数：6071 字
阅读完需：约 20 分钟

@TOC

一、快速排序

1.挖坑法

1.过程

1.为了使用方便我们默认第一个数为 key，key 的值可以看作单独提出来了，key 所在的(pivot)坑的位置先从右边开始找比 key 小的数，找到后将值传给 pivot 所在位置，同时 pivot 指向右边

2.再从左边找比 key 大的数，找到后将值传给左边 pivot 所在位置，同时 pivot 指向左边

3.当 begin 与 end 指向同一个位置时，则将关键字传入进去，循环结束

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

当递归到最后时，发现只剩下一个数或者没有数存在，而在循环中成立的条件为 lelft<right 当 left==right 时，只有一个数当 left>right 时，没有数存在

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

复制代码

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/8493247750632ea086fc1e27c】。文章转载请联系作者。

lovevivi

关注

还未添加个人签名 2022-10-12 加入

还未添加个人简介

发布

暂无评论

创作场景

八大排序 (下)

一、快速排序

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.代码实现

lovevivi

评论