【程序员必须掌握哪些算法?】

简介: 【程序员必须掌握哪些算法?】

一 .直接插入排序

直接插入排序是从一段数据中将一个数据在合适的位置插入。

案例:

一张图弄懂直接插入排序

实现代码:

void InsertSort(int * a,int n )
{
  for(int i =0;i<n-1;i++)
  {
    int end = i;
    //保存待插入元素
    int tmp = a[end+1];
    while(end>=0)
    {
      if(a[end]>tmp)
      {
        //把end往后挪
        a[end+1] = a[end];
        //end再往前走 
        end--;
      }
      else
      {
        break;
      }
    }
    //由于不管是在中间的任意地方插入还是在end的末尾插入(即tmp是最大的情况),
    //都是在end后面的位置插入,所以来到这里进行合并
    a[end+1] = tmp;
  }
}
直接插入排序时间复杂度

直接插入排序的时间复杂度为:O(N^2),因为最坏的情况是逆序的情况:

每一次插入需要挪动的次数为:1+2+3+4+…+n-2+n-1 = n*n/2

所以最坏情况下的时间复杂度为O(n^2)

二.希尔排序

希尔排序可以被认为是优化后的直接插入排序。

具体优化过程如下:

给定一个gap,这个gap是把待插入的数据分成gap组,每组之间的间隔为gap长度

给定一个gap,这个gap是把待插入的数据分成gap组,每组之间的间隔为gap长度

给定一个gap,这个gap是把待插入的数据分成gap组,每组之间的间隔为gap长度

重要的事情说三遍。

比如:

令gap = 3,即待插入的数据的间隔为3,不同于直接插入排序,直接插入排序是第一个和第二个数据的间隔永远为1,而对于希尔排序,当gap = 3时,第一个数据和第二个数据的间隔为3。

当我们把该组的元素两两比较时,大的元素就会更快地往后走。

第二轮是将待插入元素8和9比较,因为9后面的第一个元素不再是7,而是9+gap的位置处的数据,即8

再将9和8进行比较,将8插入到9位置处。

当然,这是每组组内的比较,

放眼整个希尔排序来说,是多组同时进行的

可以发现,

当gap越大,大的元素越快挪到后面
当gap越小,小的元素越慢挪到后面

当gap == 1时,就相当于上面提到的直接插入排序。

回到上面的案例,gap = 3,所以需要将数据分成3组,每组的间隔为3个长度。

如上图:此时每个元素都可以被覆盖到。

相当于同时把gap组中大的元素更快挪到后面

我们把上面的过程成为:预排序

也就是说,完成上面的操作之后,整个数据并不是有序的,而是 接近有序

比如上面的案例,完成预排序后,整组数据为:

此时是接近有序,所以此时令gap = 1,即最后接近有序的时候进行直接插入排序即可。

注意:gap的取值是不确定的:

gap取值越大,大的数据越快挪到后面,但越不接近有序

gap取值越小,大的数据越慢挪到后面,但越接近有序

总之gap是一定不能固定,并且gap的取值最后必须为1。

gap的取值应该是从大逐渐到小过渡的。

gap的取值一般是:

初始化gap = n,

进入轮回时:

gap = gap/3+1 或者 gap = gap/2,每次轮完一轮后,gap都会减小。

当gap的取值是gap = gap/2时,时间复杂度为:O(N*logN),logN是以2为底N的对数

最坏情况同样为逆序:

最后一轮gap = 1,此时为直接插入排序,则N/2/2/2/…/2 = 1,

每次轮回一次gap,gap都会/2,最后一次gap = 1,则需要比较的次数是logN(以2为底N的对数)

实现代码:

void ShellSort(int* a, int n)
{
  //当gap越大,大的值越快到达最后的位置,但越不接近有序
  //当gap越小,大的值越慢到达最后的位置,但越接近有序
  //当gap值越接近1,排序越接近顺序
  //刚gap == 1时,就是直接插入排序
  int gap = n;
  while (gap > 1)
  {
    //两种方式均可,gap可以任取任何值,但是都必须保证gap最后一定为1
    //gap = gap / 2;
    gap = gap / 3 + 1;
    //在这里就是把间隔多组的数据同时排列
    for (int i = 0; i < n - gap; i++)
    {
      int end = i;
      int tmp = a[end + gap];
      while (end >= 0)
      {
        //小于的情况,需要挪动数据
        if (a[end] > tmp)
        {
          a[end + gap] = a[end];
          end -= gap;
        }
        //大于或者等于的情况,直接插入end后面
        else
        {
          break;
        }
      }
      //由于最终都需要插入end后面,所以在循环之外插入
      a[end + gap] = tmp;
    }
  }
}

总结:希尔排序是在直接插入排序的基础上引入一个gap,这个gap把数据分成了gap组,并且每组元素之间的间隔也为gap。
gap每次都会逐渐减小,并且最后gap一定为1,当gap为1时,代表完成了预排序,
最后一步进行直接插入排序。

希尔排序时间复杂度

总的时间复杂度为遍历整组元素的次数:O(N)*每次遍历进行插入的次数O(logN)

—> O(N * logN)

同理:当gap的变化是gap = gap/3-1时, 最坏情况下(逆序)每次轮回需要插入的次数是

(((N/3+1) /3+1)/3+1)… = 1

对于时间复杂度:可忽略掉+1项,所以每次轮回插入次数log3 (N) ,以3为底N的对数

总时间复杂度为O(N*log3 (N))

经过前人计算,希尔排序平均时间复杂度为:

O(N^1.3)


前文知识清单:

三、选择排序

直接选择排序通过每一轮的比较,找到最大值和最小值,将最大值的节点跟右边交换,最小值节点跟左边交换,达到排升序的效果。

假如最左边的数据的下标为left,最右边的数据的下标为right。

选择排序就是每一轮选出max和min两个数据,将max和right下标的数据交换,将min和left下标的数据交换。交换后,right–,left++,这样第二轮就会找第二小和第二大的数据,依次往后。

实现代码:

void SelectSort(ShellDataType* a, int n)
{
  //左下标 和右下标
  int left = 0;
  int right = n - 1;
  //不需要left <= right,最后一个元素不需要再交换,当然给<=也没问题
  while (left < right)
  {
    //假设最小最大全部在left
    int mini = left, maxi = left;
    //单趟查找最小值和最大值下标
    for (int i = left; i < right; i++)
    {
      //找到最小的,更新下标
      if (a[i] < a[mini])
      {
        mini = i;
      }
      //找到最大的,更新下标
      if (a[i] > a[maxi])
      {
        maxi = i;
      }
    }
    //maxi和right交换,mini和left交换
    Swap(&a[left], &a[mini]);
    //这里存在特殊情况,如果maxi在left位置,left和mini交换了之后,最大值的下标就是mini了
    //所以这里需要判断一下,如果真的是这种情况,就更新最大值下标。
    if (maxi == left)
    {
      maxi = mini;
    }
    Swap(&a[right], &a[maxi]);
    //后面的不需要再更新了,因为后面就算mini是在right位置,这轮也已经结束了,所以不需要再管它
    //更新left和right 的下标
    left++;
    right--;
  }
}
直接选择排序时间复杂度

每一轮比较都需要遍历数组,查找最大最小值,第一轮遍历N个数据,第二轮是N-2个数据,第三轮N-4 …,遍历次数为:N+N-2+N-4+…+1,一个等差数列求和

所以总的时间复杂度为O(N^2)

四、堆排序

向上调整算法和向下调整算法请参照:数据结构——堆

所谓堆排序,就是排序堆,要求是堆才能够进行排序,所以给任意一个连续数组对数组排序的话,需要先建堆。

使用向上调整法建堆如下图:

结果如下:

时间复杂度为O(N*logN)


使用向下调整建堆如下图:

时间复杂度O(N)

堆排序:

堆排序使用交换之后再向下调整原理:

在建了大根堆之后,堆顶的左右子树都是大根堆,不管最后一个元素是否是最小的,与堆顶元素交换后,

堆顶元素就被放到了堆尾,然后再让堆顶元素向下调整,因为此时堆顶元素是一个较小的元素,会向下调整,调整之后是第二大的元素在堆顶下一次再排序时,排的是堆尾的前一个了,那个最大的元素不用再排了,排的就是第二大的元素,

再让堆的最后一个元素与堆顶元素交换,再进行向下调整,调整完后第三大的元素就上来了。

建好堆后,对堆进行排序,堆排序过程图如下:

实现代码:

void HeapSort(int* a, int n)
{
  assert(a);
  //1.先建堆,向上调整建堆,建堆的时间复杂度为O(N*logN)
  //也可以采用向下调整的方法建堆,向下调整的方法建堆的时间复杂度为O(N)
  //强烈建议采用向下调整的建堆方式
  //for (int i = 0; i < n; ++i)
  //{
  //  AdjustUp(a, i);
  //}
  //向下调整建堆,是从第一个非叶子节点开始调整,因为所有的叶子节点都不需要进行向下调整
  //child = (parent-1)/2
  //此时parent就是n-1
  for (int i = (n - 1 - 1) / 2; i >=0; -- i)
  {
    AdjustDown(a, n, i);
  }
  //现在是大根堆
  //2.堆排序,采用向下调整算法进行排序,让最后一个节点和堆顶节点进行交换,然后堆顶节点向下调整
  //调整完后继续倒数第二个节点和堆顶节点交换,以此类推
  for (int i = n-1; i >0; --i)
  {
    swap(&a[0], &a[i]);
    //这里传参不能传n,传n-1,因为交换之后最后一个数字就不需要参与进来了,相当于size--
    //堆排序使用交换之后再向下调整原理:
    //在建了大根堆之后,堆顶的左右子树都是大根堆,不管最后一个元素是否是最小的,与堆顶元素交换后
    //堆顶元素就被放到了堆尾,然后再让堆顶元素向下调整,因为此时堆顶元素是一个较小的元素,会向下调整,调整之后是第二大的元素在堆顶
    // 
    //下一次再排序时,排的是堆尾的前一个了,那个最大的元素不用再排了,排的就是第二大的元素,
    //再让堆的最后一个元素与堆顶元素交换,再进行向下调整,调整完后第三大的元素就上来了。
    AdjustDown(a, i, 0);
  }
  //总结:排升序的话,建大根堆
  //排降序建小根堆
  for (int i = 0; i < n; i++)
  {
    printf("%d ", a[i]);
  }
}
堆排序时间复杂度

建堆的时间复杂度为O(N)

调整过程遍历N个数的时间复杂度为O(N)

每次调整一个数的时间复杂度为O(logN)

总的时间复杂度为O(N+N*logN)

综上:

堆排序的时间复杂度为:O(N*logN)

五、冒泡排序

冒泡排序(Bubble Sort):一次比较两个元素,如果他们的顺序错误就把他们交换过来,重复道数列已经不用再交换。冒泡排序名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。相当于升序操作。

每一趟冒泡排序,就排序一个数,可以形象地认为把一个大的数字放到水底,把小的数放在水面,慢慢冒出泡泡来。

冒泡排序实现代码:

void bubble_sort(int* arr, int sz)
{
  int i = 0;
  for (i = 0; i < sz - 1; i++)
  {      //sz-1是冒泡排序的趟数
    int j = 0;
    for (j = 0; j < sz - 1 - i; j++)
    {    //sz-1-i是每一趟冒泡排序要比较的元素个数
      if (arr[j] > arr[j + 1])//升序排序
      {
        int tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    }
  }
}

我们发现:当冒泡排序中只有某少数个数据是无序的时候,当进行完了一趟排序,整个数据就有序了,这时候就不需要再比较了。

当进行了一轮排序后,此时数据已经有序,就可以退出不再比较了。

所以冒泡排序还可以进行优化:

void buuble_sort(int arr[], int sz)
{
  int i = 0;
  for (i = 0; i < sz; i++)
  {
    int j = 0;
    int flag = 1;//假设这一趟冒泡排序已经有序
    for (j = 0; j < sz - 1 - i; j++)
    {
      if (arr[j] > arr[j + 1])
      {
        int tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
        flag = 0;//如果没完全有序,则flag=0,我们才能知道是否完全有序
      }
    }
    if (flag == 1)
    {
      break;
    }
  }
}
冒泡复杂度

1. 时间复杂度:O(N^2)

2. 空间复杂度:O(1)

3. 稳定性:稳定

六、快速排序

(以下为递归法)

快速排序是一种类似二叉树结构的排序。

思路: 在待排序数据中任取一个值作为基准值(key),按照一定的方式,将比key值小的数据放到左边,比key值大的放到右边,达到key值就是一个分割点,其左边比它小,右边比它大。然后以key为分割点分别对其左子区间和右子区间进行同样的操作。

1.Hoare法(不推荐)

Hoare法是快排的创始人Hoare提出的方法,这个方法有点难以理解,且有许多细节需要注意,不是很推荐该方法。

思路是:

给定两个下标,分别为left和right,记录最左边的下标和最右边的下标。选取一个值作为key(一般选最左边或者最右边的值作为key),其下标为keyi,如果是选左边做key,就让right先走,如果是选右边做key,就让左边先走。

假设选左边做key,right先走,找比key小的值,如果找到了,然后轮到左边left走,左边left找大,如果找到了,就交换left和right下标所对应的值。然后再重复该过程。

第一步:

第二步:

第三步:递归,先递归keyi的左边,再递归keyi的右边。

重复上述操作。

但是Hoare存在几个缺陷:

缺陷1.当数据为有序或者逆序的时候,我们每次选key都是选最左边或者最右边,这就导致了每排序完一次,keyi的位置仍然是最左边或者最右边,此时递归的次数就要递归n次,可能会导致栈溢出。

选基准值key的方法(快排的方法均可用)

所以我们需要每次去key的时候尽量取到中间的数,保证递归下去左右两个子区间是比较均匀的。

1、随机法

此时出现了两种取key的方法:

1.随机取key法:就是随机取一个key。

// 随机选key
  int randi = left + (rand() % (right - left));
  //随机选到key后,把key放到左边的位置
  Swap(&a[left], &a[randi]);
2. 三数取中(推荐)

2.(推荐)三数取中法,三数取中法就是以left,right,mid为下标的三个数取一个中间大的数作为key。

比如说:

mid = (left+right)>>1 ;

a[left] = 6,a[right] = 8,a[mid] = 3;所以应该取的数是6。这样就保证了每次取到的数是比较中间的数,就不会出现当数据为顺序时递归深度太深出现栈溢出的情况。

//三数取中法取key
//从左,右,中三个数选出一个不大不小的数作为key
int GetMidNumi(int *a, int left, int right)
{
  int mid = (left + right) / 2;
  //也可以这样写 , 右移一位除2,左移一位乘2,左移两位乘2^2,以此类推
  //int mid = (left + right) >> 1;
  if (a[left] < a[right])
  {
    if (a[left] > a[mid])
    {
      return left;
    }
    else if(a[right] < a[mid])
    {
      return right;
    }
    else
    {
      return mid;
    }
  }
  else
  {
    if (a[right] > a[mid])
    {
      return right;
    }
    if (a[mid] > a[left])
    {
      return left;
    }
    else
    {
      return mid;
    }
  }
}

缺陷2、

前面说过,当用left作为key值时,right先走,且right找小,找到小了到left找大。

即:

while (left < right)
  {
    while (a[right] > a[keyi])
      --right;
    while (a[left] < a[keyi])
      ++left;
    Swap(&a[left], &a[right]);
  }

当排序的数据为 6 1 2 6 9 3 4 6 10 8 时,right向左边找小,找到的数据为6,left找大,找到的数据也为6,此时交换left和right之后,还是6不变,又重新循环right找小,left找大,这样永远会循环在6这个位置互相交换,就会出现死循环。

解决办法是加个等号。

如下:

while (left < right)
  {
    while (a[right] => a[keyi])
      --right;
    while (a[left] <= a[keyi])
      ++left;
    Swap(&a[left], &a[right]);
  }

缺陷3:

如果排序的数是 1 2 3 4 5

此时选1做key,先right找小,就会不断–,–这样会出现–到比left还小,就会出问题。

综合来看,需要这样改进:

while (left < right)
  {
    while (left < right && a[right] => a[keyi])
      --right;
    while (left < right && a[left] <= a[keyi])
      ++left;
    Swap(&a[left], &a[right]);
  }
小区间优化(每种方法都可用)

了解小区间优化之前, 我们需要知道一个问题:

当数据量很大的时候,比如有一千万个数据,我们需要对其进行排序:

使用递归的方法进行排序,难免出现递归深度深而出现效率降低的情况。

根据上图的情况可知,理想情况下,当有N个数据时,最小的递归深度是LogN。
此时,最后一层的递归次数是最多的,需要递归N/2次,也就是说,有100W个数据时,最后一层需要递归50W次!!那么倒数第二层需要递归25W次,倒数第三层需要递归12.5W次,假如我们能够把最后三层递归的次数消去,既能提高效率,也能减小递归消耗的栈空间。

所以当数据个数为10个以下时,就不需要用快排了,我们可以用直接插入排序来代替快排。

这就是为什么你在下面的代码能够看到当数据个数小于10,用插入排序的原因。

Hoare实现代码
void QuickSort1(SortDataType* a, int left, int right)
{
  //递归结束条件
  if (left >= right)
    return;
  int keyi = PartSort1(a, left, right);
  //递归下去
  // [left, keyi-1] keyi [keyi+1, right] 
  //小区间优化,如果数据个数小于10个,用直接插入排序
  if (keyi - left + 1 <= 10)
  {
    InsertSort(a + left, keyi - left + 1);
  }
  else
  {
    QuickSort1(a, left, keyi - 1);
  }
  if (right - (keyi + 1) + 1 <= 10)
  {
    InsertSort(a + keyi + 1, right - (keyi + 1) + 1);
  }
  else
  {
    QuickSort1(a, keyi + 1, right);
  }
}
 // //Hoare
int PartSort1(SortDataType* a, int left, int right)
{
   随机选key
  //int randi = left + (rand() % (right - left));
  随机选到key后,把key放到左边的位置
  //Swap(&a[left], &a[randi]);
  // 三数取中
  int midi = GetMidNumi(a, left, right);
  //把key值挪到left位置
  if (midi != left)
    Swap(&a[midi], &a[left]);
  //出现了随机选key和三数取中选key的原因:假如要排的数是已经有序或者完全逆序,
  //使用固定的选left下标的值为key的话,快排的时间复杂度就是O(N^2)
  //为了优化快排,就采取随机选key或者三数取中的方法
  //这是一轮
  //铁律:左边做keyi值右边先走,右边做key值左边先走,能保证L和R相遇位置一定比keyi小
  //原因:情况1.R先走,找小,找到了,然后到L走,L找大,找到了,交换
  //L和R相遇的位置,就一定是比key小的
  int keyi = left;
  while (left < right)
  {
    //排升序
    //右边找小
    //必须要给定left<right这个条件,否则如果是1 2 3 4 5这组数据,right会--到越界
    //必须要给等于号,否则可能会死循环
    //比如这组数据: 5 1 2 5 8 9 5 6 8
    //停下来的位置都是跟key相同的,两个相同的交换还是一样,就产生了死循环
    while (left < right && a[right] >= a[keyi])
      --right;
    //左边找大
    //必须要给定left<right这个条件,否则如果是5 4 3 2 1这组数据,left会++到越界
    while (left < right && a[left] <= a[keyi])
      ++left;
    //找到之后交换,实现了比key小的在左边,比key大的在右边
    Swap(&a[left], &a[right]);
  }
  //退出循环就是left == right 了,那就交换keyi和left或者keyi和right都行
  Swap(&a[keyi], &a[left]);
  // [begin, keyi-1] keyi [keyi+1, end] 
  //完成了一轮排序,找到了一个keyi,返回
  //注意,返回的是下标,此时keyi经过交换之后,key的下标在left/right位置
  //所有返回的是left/right,而不是返回keyi,或者你可以更新keyi然后返回
  keyi = left;
  return keyi;
}

2.挖坑法(推荐)

挖坑法:顾名思义,挖坑,填坑的过程。

思路:

首先选取一个key(三数取中),选出来保存之后,left就留下了一个坑位,(在实际的数据中left下标对应的值仍然存在,这里的填坑本意是覆盖),于Hoare法相似,左边做key,right先走,找比key小的,找到之后放在left这个坑位中,此时right又形成了一个新的坑位,然后轮到left找大,left找到之后,将数填入right这个坑中,此时left又形成了新的坑位,这样循环,直到left和right相遇。

结果:保证了key的左边比key小,右边比key大。然后再递归key的左右子区间即可。

实现代码:
//挖坑法的难点在于key只是一个临时变量,hole是坑的下标,变量和下标易于混淆
//右边找小左边找大的过程中,可能出现右边找小找不到最后找出数组范围了,所以要限制left<right
//同理左边找大也是
//挖坑法
void QuickSort2(SortDataType* a, int left, int right)
{
  //递归结束条件
  if (left >= right)
    return;
  int begin = left, end = right;
  // 三数取中
  int midi = GetMidNumi(a, left, right);
  //把key值挪到left位置
  if (midi != left)
    Swap(&a[midi], &a[left]);
  //这个key只是一个临时变量
  int key = a[left];
  int hole = left; // 坑位
  while (left < right)
  {
    // 右边找小
    while (left < right && a[right] >= key)
      right--;
    //找到了,填坑
    a[hole] = a[right];
    hole = right;
    // 左边找大
    while (left < right && a[left] <= key)
      left++;
    //找到了,填坑
    a[hole] = a[left];
    hole = left;
  }
  //把key放到最后的坑里面
  a[hole] = key;
  if (hole - 1 - begin <= 10)
  {
    InsertSort(a + begin, hole - 1 - begin + 1);
  }
  else
  {
    QuickSort2(a, begin, hole - 1);
  }
  if (end - hole + 1 <= 10)
  {
    InsertSort(a + hole + 1, end - hole + 1 +1);
  }
  else
  {
    QuickSort2(a, hole + 1, end);
  }
}

3. 前后指针法(力荐)

前后指针法是相对来说最好实现,细节不需要考虑那么多的方法。

思路:首先,给定两个下标prev和cur(说是前后指针法,是为了方便理解,其实指针法也不一定非得要指针) ,prev存left位置的下标,cur = prev 的下一个位置的下标。

key也是使用三数取中法来求key,然后放到left位置。

其次:cur先走,往后找比key小的;

1.如果比key小,先++prev,再交换cur和prev对应的值,最后++cur。

2.如果比key大,直接++cur。

这样不断循环,直到cur大于right为止。

最后将keyi对应的key和prev对应的值交换。(重点)

实现了比key小的在左边,比key大的在右边。

你会发现prev和cur就像一个车轮,不断将比key小的数转到左边,比key大的数转到右边。

实现代码
void QuickSort3(SortDataType* a, int left, int right)
{
  //递归结束条件
  if (left >= right)
    return;
  int begin = left, end = right;
  //三数取中法求key
  int midi = GetMidNumi(a, left, right);
  if(midi!=left)
    Swap(&a[midi], &a[left]);
  int keyi = left;
  int prev = left;
  int cur = prev + 1;
  while (cur <= right)
  {
    //也可以这样写
    if (a[cur] < a[keyi] && ++prev != cur)
      Swap(&a[prev], &a[cur]);
    ++cur;
    //下面这样写逻辑比较清晰,好懂
    //if (a[cur] < a[keyi])
    //{
    //  ++prev;
    //  //自己跟自己没有交换的必要,浪费时间
    //  if(cur != prev)
    //    Swap(&a[prev], &a[cur]);
    //  ++cur;
    //}
    //else
    //{
    //  ++cur;
    //}
  }
  //切记不能交换
  //Swap(&a[prev], &key);
  //key只是一个临时变量,交换了它,跟没交换一样,因为跟临时变量交换与数组的交换无关
  Swap(&a[prev], &a[keyi]);
  keyi = prev;
  if (keyi - 1 - begin + 1 <= 10)
  {
    InsertSort(a, keyi - 1 - begin + 1);
  }
  else
  {
    QuickSort3(a, begin, keyi - 1);
  }
  if (end - (keyi + 1) + 1 <= 10)
  {
    InsertSort(a, end - (keyi + 1) + 1);
  }
  else
  {
    QuickSort3(a, keyi + 1, end);
  }
}

快速排序非递归法

思路:对于递归方法来说,每次递归左右子区间需要建立栈帧,所以我们的非递归方法可以模拟递归的栈。

建立一个栈。

首先将left和right下标入栈,由于栈的特性是后进先出,所以需要先入right再入left。

(如果不想考虑那么多,可以用一个结构体存储left和right的下标。(这个可以下去尝试))

取出栈顶的left和right元素后,使用上面的三种排序方法中的任意一种来进行第一轮排序。 第一轮排序完成后, 就获得了下面的区间:

【left, keyi-1】 keyi 【keyi+1,right】

类似栈一样,先递归左子区间,所以需要先入栈右子区间,再入栈左子区间。

(栈是后进先出的特性)

不断入栈出栈的过程就实现了快排的递归。

栈代码
void StackInit(ST* ps)//初始化
{
  assert(ps!=NULL);
  ps->a = NULL;
  ps->top = ps->capacity = 0;
  //ps->top可以初始化成-1,此时先++,再赋值
  //此时指向的就是栈顶元素
}
void StackDestroy(ST* ps)
{
  assert(ps);
  free(ps->a);
  ps->a = NULL;
  ps->top = ps->capacity = 0;
}
void CheckCapacity(ST**ps)//检查容量
{
  assert(ps != NULL);
  if ((*ps)->top == (*ps)->capacity)
  {
    STDataType newcapacity = (*ps)->capacity == 0 ? 4 : (*ps)->capacity * 2;
    STDataType* tmp = (STDataType*)realloc((*ps)->a,(sizeof(STDataType)*newcapacity));//申请的空间是存放STDataType的
    //不是用来存放结构体的
    //如果第一个参数是一个NULL,realloc的作用就跟malloc一样,所以可以传NULL
    assert(tmp != NULL);
    (*ps)->a = tmp;// 把新地址给ps->a
    (*ps)->capacity = newcapacity;
  }
}
void StackPush(ST* ps, STDataType x)//插入元素
{
  assert(ps);
  CheckCapacity(&ps);//这里如果传参传的是ps,相当于传值调用,在CheckCapacity函数内部申请的空间就无法返回来了。
  ps->a[ps->top] = x; // 先赋值,再++,因为ps->top初始化是0,就是指向栈顶元素的下一个。
  ps->top++;
}
void StackPop(ST* ps)//删除栈顶数据
{
  assert(ps);
  assert(!StackEmpty(ps));
  ps->top--;
}
STDataType StackTop(ST* ps)//取栈顶元素
{
  assert(ps);
  assert(!StackEmpty(ps)); //感叹号表达式让语句的逻辑相反
  return ps->a[ps->top - 1];
}
int StackSize(ST* ps)//计算栈有多少个数据
{
  assert(ps);
  assert(!StackEmpty(ps));
  return ps->top;
}
bool StackEmpty(ST* ps)//判断栈是否为空
{
  assert(ps);
  return ps->top == 0;
}
//快排非递归写法:模拟栈实现非递归
//思路:先求出一个keyi出来,然后分成左右两个子区间,分别入栈,入栈先入右区间再入左区间
//
int PartSort3(SortDataType* a, int left, int right)
{
  //三数取中法求key
  int midi = GetMidNumi(a, left, right);
  if (midi != left)
    Swap(&a[midi], &a[left]);
  int keyi = left;
  int prev = left;
  int cur = prev + 1;
  //1.cur指针指向的位置如果小于key,先++prev,然后Swap(cur,prev),然后再++cur
//2.cur指针指向的位置如果大于key,直接++cur
  while (cur <= right)
  {
    //也可以这样写
    if (a[cur] < a[keyi] && ++prev != cur)
      Swap(&a[prev], &a[cur]);
    ++cur;
    //下面这样写逻辑比较清晰,好懂
    //if (a[cur] < a[keyi])
    //{
    //  ++prev;
    //  //自己跟自己没有交换的必要,浪费时间
    //  if(cur != prev)
    //    Swap(&a[prev], &a[cur]);
    //  ++cur;
    //}
    //else
    //{
    //  ++cur;
    //}
  }
  //切记不能交换
  //Swap(&a[prev], &key);
  //key只是一个临时变量,交换了它,跟没交换一样,因为跟临时变量交换与数组的交换无关
  Swap(&a[prev], &a[keyi]);
  //更新keyi的下标
  keyi = prev;
  return keyi;
}
void QuickSortNonR(SortDataType* a, int left, int right)
{
  ST st;
  StackInit(&st);
  //入的时候是先右后左
  StackPush(&st, right);
  StackPush(&st, left);
  while (!StackEmpty(&st))
  {
    //出的时候是先左后右
    int begin = StackTop(&st);
    StackPop(&st);
    int end = StackTop(&st);
    StackPop(&st);
    //划分区间,这里的PartSort3其实就是第三种前后指针法分出来的
    int keyi = PartSort3(a, begin, end);
    //只有一个数据的时候就不用入栈了
    if (keyi + 1 < end)
    {
      StackPush(&st, end);
      StackPush(&st, keyi + 1);
    }
    if (begin < keyi - 1)
    {
      StackPush(&st, keyi - 1);
      StackPush(&st, begin);
    }
  }
  //当栈空了就排完了
  StackDestroy(&st);
}
快排复杂度

快排每排序一次,需要遍历n个数据,递归深度是logN,最坏情况下递归深度为N,所以最坏情况时间复杂度为O(N^2)。

但是快排可以优化,优化后递归的最大深度为N,所以快排时间复杂度为O(NlogN)

空间复杂度O(LogN)~O(N) (其中O(N)是最坏情况)

稳定性:不稳定


七、归并排序

归并排序是将一段区间分成若干个子问题,子问题再次分成子问题,这个是分治过程;最后分成的子问题只存在一个数时,就可以开始合并,合并的过程就是比较两个子问题的过程,合并完成后将合并的新数据拷贝到原数据即可。

递归实现归并排序

递归实现归并排序,就是把一个大的数组分治分治,不断分治下去成一个小的数组,

最后分治成只有一个数字为止,然后每一个数字之间两两合并成2个数字,两组数组的两个数字之间再合并成4个数字,以此类推,知道合并成最后一个大的数组为止。

第一步:通过left和right下标找到数组中间位置的下标,以该下标为界限,划分成两组数据。

第二步:重复第一步的过程,但是先把左边的组彻底分完,再分右边的组,是二叉树的前序遍历的思想。

第三大步:不断进行分治,直到分解到还剩一个元素时停下来,判断只有一个元素,就是当left>=right时。

第四步:两两比较,四四比较合并

注意:每次合并完都需要把tmp的数据拷贝回原数组。

最后一步:两个子区间合并成总的区间:

注意:每次合并完都需要把tmp的数据拷贝回原数组。

实现代码:
void _MergeSort(SortDataType* a, int left, int right, SortDataType* tmp)
{
  if (left >= right)
  {
    return;
  }
  int mid = (left + right) >> 1; // 右移一位相当于/2
  int begin1 = left, end1 = mid;
  int begin2 = mid + 1, end2 = right;
  int index = left; // tmp的下标,不能从0开始,因为有些归并是不会从0开始的。
  _MergeSort(a, begin1, end1, tmp);
  _MergeSort(a, begin2, end2, tmp);
  while (begin1 <= end1 && begin2 <= end2)
  {
    if (a[begin1] <= a[begin2])
    {
      tmp[index++] = a[begin1++];
    }
    else
    {
      tmp[index++] = a[begin2++];
    }
  }
  //到这里不知道是谁先结束的,所以都要判断
  while (begin1 <= end1)
  {
    tmp[index++] = a[begin1++];
  }
  while (begin2 <= end2)
  {
    tmp[index++] = a[begin2++];
  }
  //拷贝回去
  //for (int i = left; i <= right; ++i)
  //{
  //  a[i] = tmp[i];
  //}
  // source, destination , size
  //每次归并完都拷贝一次
  memcpy(a + left, tmp + left, sizeof(SortDataType) * (right - left + 1));
}
void MergeSort(SortDataType* a, int n)
{
  SortDataType* tmp = (SortDataType*)malloc(sizeof(SortDataType) * n);
  _MergeSort(a, 0, n - 1, tmp);
}

非递归实现归并排序

对于递归实现归并排序来说,是把大问题分成小问题,是自上往下分的。

而对于非递归来说,是从小问题开始合并成大问题,是从下往上分的。

以上面的数字为例:

大致思路如下:

非递归难点1:

但面临第一个问题:

如何选择从一一开始比较到两两开始比较

选择用gap

gap表示每次归并时每组的数据个数

初始时gap = 1,表示第一次是一一比较,每合并完一轮,gap*2,下一轮进行两两比较,以此类推。

非递归难点2:

不过,第二个理解的难点在于:begin1和end1,begin2和end2该如何选择的问题!

首先是i每次跳跃2×gap,因为一开始是一一比较,比较完一次相当于比较了两个数据,

而gap的含义就是每次合并时每组的数据个数!

那么就需要跳过2 ×gap的长度。

其次是begin1 和end1,begin1 = i 好理解;

end1 = i+gap-1是这样的:i+gap表示从begin1开始的往后的gap个数据, 由于是数据,那么-1才是下标。

而begin2 = i+gap也好理解,end1的后面一个就是begin2;

end2 = i+2*gap-1,就是从i位置开始,跳跃2×gap的数据个数到达最后一个需要比较的数据,-1就是这个最后的数据的下标。

非递归难点3:

难点3在于边界如何处理

先讲讲归并完一串数字如何拷贝回原数组:

1.一次性拷贝法,也叫梭哈拷贝法(不推荐)
2.每合并一次,就拷贝一次(推荐)

1.梭哈拷贝法:就是到合并完所有的数据之后再一次性拷贝回原数组,简单粗暴。

2.每合并一次就拷贝一次:在一一合并成两个有序数据之后,就拷贝会原数组。

这里的边界有三种情况:

第一种:end1越界了,如下情况,当合并到四四比较时,begin1刚好为末位置,那么end1开始都越界了:

这里的处理方法有两种,但不同的方法是根据如何将归并好的数据拷贝回原数组决定的。

如果是梭哈拷贝法,不管哪种情况,都要修正过来。

先说end1越界的情况,如果是采用梭哈拷贝法一次性拷贝会原数组,就要让end1修正到

end1 = n-1 ,让begin2和end2修正到一个不存在的区间,比如:

begin2 = n ,end2 = n-1。这样做的目的是不让begin2、end2这个区间进入循环,防止拷贝到界外的数据。

如下:

begin2 和end2的修正当然不唯一,只要修正到一个不存在的区间即可。

第二种:begin2越界

可能发生的begin2越界如下:

第二种情况处理方式与第一种相同,在梭哈拷贝法的前提下,需要修正begin2 、end2这两个数据到一个不存在的区间,防止它们被拷贝。

比如:begin2 = n,end2 = n-1。

如下:

第三种:end2越界

此时只需要把end2修正到n-1位置即可,

如下:

注意:begin1是不可能越界的,begin1是不可能越界的,begin1是不可能越界的,因为如果begin1越界了,那后面的end1,begin2,end2全都越界了,那还归并啥!

实现代码

梭哈写法代码如下:

void MergeSortNonR(SortDataType* a, int n)
{
  SortDataType* tmp = (SortDataType*)malloc(sizeof(SortDataType) * n);
  assert(tmp);
  int gap = 1;
  //gap 是归并过程中,每组数据的个数
  while (gap < n)
  {
    for (int i = 0; i < n; i+=2*gap)
    {
      //理解难点
      //当gap为2时,i每次都会走2步,相当于跳过一个归并组
      int begin1 = i, end1 = i + gap - 1;
      int begin2 = i + gap, end2 = i + 2 * gap - 1;
      int index = i;
      //梭哈修正写法,但是不推荐
      if (end1 >= n)
      {
        end1 = n - 1;
        begin2 = n;
        end2 = n - 1;
      }
      else if (begin2 >= n)
      {
        begin2 = n;
        end2 = n - 1;
      }
      else if (end2 >= n)
      {
        end2 = n - 1;
      }
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (a[begin1] <= a[begin2])
        {
          tmp[index++] = a[begin1++];
        }
        else
        {
          tmp[index++] = a[begin2++];
        }
      }
      //到这里不知道是谁先结束的,所以都要判断
      while (begin1 <= end1)
      {
        tmp[index++] = a[begin1++];
      }
      while (begin2 <= end2)
      {
        tmp[index++] = a[begin2++];
      }
    }
    //不推荐
    //法1:梭哈法:一次性整体拷贝 
    memcpy(a, tmp, sizeof(SortDataType) * n);
    gap *= 2;
  }
  free(tmp);
  tmp = NULL; 
}

二、如果是每归并一次,就拷贝一次数据回到原数组的拷贝方法的话,处理情况就不同。

在合并一次拷贝一次的情况下:

1.end1 越界了

因为是合并一次拷贝一次,则前面的红色的数据已经全部从tmp临时数组拷贝回到原数组了,至于3这个数据,不需要再拷贝到tmp了,让他留在原来的地方即可。

所以处理方法是直接break

2.begin2 越界了

与end1越界的情况相同,因为是合并一次拷贝一次,则前面的红色的数据已经全部从tmp临时数组拷贝回到原数组了,至于后面的数据,不需要再拷贝到tmp了,让他留在原来的地方即可。

所以直接break

3.end2越界

同样的,如果是end2越界,就需要修正end2到n-1位置,保证begin1 和begin2可比即可。

所以修正 :end2 = n-1

走一步拷贝一步的非递归写法如下:

void MergeSortNonR(SortDataType* a, int n)
{
  SortDataType* tmp = (SortDataType*)malloc(sizeof(SortDataType) * n);
  assert(tmp);
  int gap = 1;
  //gap 是归并过程中,每组数据的个数
  while (gap < n)
  {
    for (int i = 0; i < n; i+=2*gap)
    {
      //理解难点
      //当gap为2时,i每次都会走2步,相当于跳过一个归并组
      int begin1 = i, end1 = i + gap - 1;
      int begin2 = i + gap, end2 = i + 2 * gap - 1;
      int index = i;
      //法2:三种情况,但是前两种情况可以使用相同的方法解决
      //如果end1越界了,那就不归并了,
      //如果begin2越界了,那也不归并了
      if (end1 >= n || begin2 >= n)
      {
        break;
      }
      //如果end2越界了,让end2修正到n-1位置
      if (end2 >= n)
      {
        //修正
        end2 = n - 1;
      }
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (a[begin1] <= a[begin2])
        {
          tmp[index++] = a[begin1++];
        }
        else
        {
          tmp[index++] = a[begin2++];
        }
      }
      //到这里不知道是谁先结束的,所以都要判断
      while (begin1 <= end1)
      {
        tmp[index++] = a[begin1++];
      }
      while (begin2 <= end2)
      {
        tmp[index++] = a[begin2++];
      }
      // destination  source  size
      //推荐
      //法2:归并一点,拷贝一点,需要画图理解
      //如果是end1 或begin2大于等于n的时候越界
      //不同于梭哈一次性拷贝,梭哈拷贝需要把所有的拷贝进tmp,必须再拷回去,虽然做了无用功,但是是必须做的,这也是比较挫的地方
      //这个法2没做无用功,既然end1或者begin2越界了,那就干脆不拷贝了
      memcpy(a + i, tmp + i, sizeof(SortDataType) * (end2 - i+1));
    }
    gap *= 2;
  }
  free(tmp);
  tmp = NULL; 
}

注意两种写法中,拷贝的代码放在了while循环的不同位置!

归并排序复杂度

归并排序具有稳定性,即对于两个及以上的相同数据,归并排序前后不会改变相同数据的相对位置,这个就是稳定性。

归并排序对数据的顺序是不敏感的。

归并排序时间复杂度为O(NlogN),从一一归并开始,每次归并都需要遍历所有数据,但由于是二路归并,所以n个数据的 ”高度“是logN,即没进行一层,就需要遍历一次所有数据,所以时间复杂度就是O(NlogN).

空间复杂度:O(N),因为需要开辟一个临时数组来保存合并好的值,所以空间复杂度是O(N).

八、计数排序

计数排序是对每个数据进行计算出现的次数的排序。

这里引入了绝对映射和相对映射的概念。先讲绝对映射:

绝对映射就是:针对一组数据,先遍历找出该组数据的最大值,开辟一块最大值+1的空间,用来对每个数据进行遍历计数。

获得每个数据出现的次数后,通过按顺序遍历Count这个计数数组,就可以对该数据进行排序了。

但是这里有一个问题,假如这组数据是 :

1 0 0 1 1 0 2 99999

那么我们开辟的空间是这组数据的最大值+1,也就是要开辟10W块空间!

这是一个惊人的数字,这样做消耗了大量的空间,有一种方法可以解决这样的问题:

相对映射可以解决。

相对映射就是,遍历一遍数据,找出max和min, 我们只需要开辟max-min+1的空间就足够了!

假如我们需要排序这样的数据

10 20 11 14 15 11 17 19 13

第一步:先遍历找出max 和min ,此时max = 30,min = 10

那么我们只需要开辟 max - min +1的空间就可以了。

这一块空间包含了所有在最大和最小值之间的值了。

相对映射处理法:

所以在排序较为集中的数据的时候,计数排序效率是最高的,甚至比快速排序还要高。

实现代码:

void CountSort(SortDataType* a, int n)
{
  int min = a[0];
  int max = a[0];
//找max和min
  for (int i = 1; i < n; ++i)
  {
    if (min > a[i])
    {
      min = a[i];
    }
    if (max < a[i])
    {
      max = a[i];
    }
  }
  //calloc(num,size) ,自动初始化为0
  int range = max - min+1;
  //这里必须是max - min +1,假如max = 10,min = 0,max-min = 10,但是实际上有11个数据。
  //左闭,右闭区间,需要+1
  SortDataType* Count = (SortDataType*)calloc(range, sizeof(SortDataType));
  if (Count == NULL)
  {
    perror("malloc fail\n");
    exit(-1);
  }
  //计数
  for (int i = 0; i < n; ++i)
  {
    Count[a[i] - min]++;
  }
 //拷贝回原数组
  int j = 0;
  for (int i = 0; i < range; i++)
  {
    while (Count[i]--)
    {
      a[j++] = i+min;
    }
  }
}

计数排序也有缺点:计数排序更加适合那些排序的数据较为集中的数据,并且计数排序不能排浮点数,结构体这样的类型,只能排序整型。

计数排序复杂度

时间复杂度:遍历一遍数组找max和min,为O(N)

再遍历一遍数组进行计数,为O(N)

将计数后的数据按顺序放会原数组,为O(N)

所以计数排序时间复杂度为O(N)

开辟max-min+1个空间

空间复杂度为O(max-min+1)

八大排序总结:

稳定性是:一组数据进行了某种排序后,相同的元素的相对位置不改变,则该排序就是稳定的。比如:一组数据为: 2 1 5 9 3 5,如果两个5的相对位置没有改变,那就稳定。

判断排序算法是否稳定,需要回忆算法的思想,该算法是如何做到排序的过程。

冒泡排序:稳定。

原因:两两比较,然后进行交换,对于相同的数据,如果不交换,就可以做到稳定了。

直接选择排序:不稳定。

原因:假如一组数据为: 2 2 1 3 1,第一轮,选出最小的和最大的,然后分别和left和right下标对应的值交换,那么交换后第一个2 和第二个2的相对位置就改变了。

直接插入排序:稳定。

原因:对于相同的数,直接插入在其后面即可。可以做到稳定。

希尔排序:不稳定。

原因:在进行预排序的时候,相同的数据可能被分到不同的组,预排序完成后相同的数据的相对位置可能改变。

堆排序:不稳定。

原因:建堆过程就不稳定,假如建堆没有改变相同的数的相对顺序,那么堆排序的过程,假设建大根堆,那么根位置的数据与最后一个数据交换后,此时堆顶的元素是比较小的,需要向下调整,调整过程中也会出现相同数据的相对位置改变的情况。

归并排序:稳定。

原因:只要相同的元素不比较即可。

快排:不稳定。

原因:假如一组数据是这样的分布:

在排完一趟后,最后一步需要将left和中间的某一个keyi应该在的位置交换,就造成了相对位置不同的问题。

三:重点算法总结

通过学习掌握算法设计的主要方法,对算法的时、空复杂性有正确分析的能力,能够针对具体的应用问题选择合适的数据结构并设计结构清晰、正确有效的算法,为独立设计算法和对算法进行复杂性分析奠定坚实的理论基础。

相关文章
|
1月前
|
负载均衡 监控 算法
每个程序员都应该知道的 6 种负载均衡算法
每个程序员都应该知道的 6 种负载均衡算法
115 2
|
2月前
|
算法 程序员 Python
程序员必看!Python复杂度分析全攻略,让你的算法设计既快又省内存!
在编程领域,Python以简洁的语法和强大的库支持成为众多程序员的首选语言。然而,性能优化仍是挑战。本文将带你深入了解Python算法的复杂度分析,从时间与空间复杂度入手,分享四大最佳实践:选择合适算法、优化实现、利用Python特性减少空间消耗及定期评估调整,助你写出高效且节省内存的代码,轻松应对各种编程挑战。
41 1
|
3月前
|
算法 搜索推荐 程序员
程序员常用算法详细讲解
每一种算法都有其适用场景,了解并熟悉这些常用算法的策略和实现,对于解决实际编程问题具有重要的意义。需要注意的是,理论知识的重要性虽然不言而喻,但真正的理解和掌握,还需要在实践中不断地尝试和错误,以达到深入理解的目的。
29 1
|
3月前
|
机器学习/深度学习 算法 搜索推荐
程序员必须掌握的算法
作为一名程序员,掌握一些重要的算法是必不可少的。算法是解决问题的方法和步骤,对于程序员来说,熟悉和掌握一些常见的算法可以提高编程能力,解决复杂的计算问题。与此同时,算法是计算机科学中的核心概念,对于程序员来说,掌握一些基本的算法是非常重要的。
50 1
|
5月前
|
算法 程序员
程序员必知:XGB算法梳理
程序员必知:XGB算法梳理
31 0
|
5月前
|
算法 JavaScript 程序员
程序员必知:《程序设计与算法(二)算法基础》《第一周枚举》熄灯问题POJ
程序员必知:《程序设计与算法(二)算法基础》《第一周枚举》熄灯问题POJ
34 0
|
6月前
|
机器学习/深度学习 人工智能 算法
每个程序员都应该知道的 40 个算法(四)(3)
每个程序员都应该知道的 40 个算法(四)
47 2
|
6月前
|
机器学习/深度学习 算法 数据挖掘
每个程序员都应该知道的 40 个算法(四)(4)
每个程序员都应该知道的 40 个算法(四)
48 1
|
6月前
|
NoSQL 算法 Java
【redis源码学习】持久化机制,java程序员面试算法宝典pdf
【redis源码学习】持久化机制,java程序员面试算法宝典pdf
下一篇
无影云桌面