八大排序 (上)

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

一、直接插入排序

1.概念

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列

2.直接插入排序的实现

void insertsort(int* a, int sz)//直接插入排序   [0 end]有序，插入end+1位置的值让[ 0 end+1]也有序{  int i = 0;//假设我们要排升序  for (i = 0; i < sz - 1; i++)//i不能取到sz-1 否则tmp就会造成越界访问  {    int end = i;    int tmp = a[end + 1];//后一个数据    while (end >= 0)    {      if (a[end] > tmp)//如果数组中的数据大于tmp      {        a[end+1] = a[end];        end--;      }      else      {        break;//找到比tmp小的就结束循环      }    }    a[end + 1] = tmp;//为了防止tmp比所有数据都小这种情况发生  }  }

复制代码

直接插入排序的时间复杂度

二、希尔排序

1.概念

思想为：先选定一个整数，把待排序文件中所有记录分组，所有距离内的记录在同一组中，再对每一组内的记录进行排序，重复分组和排序，直到=1 时结束.

希尔是直接插入排序的优化 1.先进行预排序,让数组接近有序 2.直接插入排序

此时发现：多组间隔为 gap 的预排序，gap 由大变小 gap 越大，大的数越快到后面，小的数越快到前面 gap 越大，预排完，越不接近有序，gap 越小，预排完，越接近有序当 gap=1 时，就时直接插入排序

2. 希尔排序的实现

void shellsort(int* a, int n)//希尔排序{  int i = 0;  int gap = n;  while (gap > 1)  {    gap = gap / 3 + 1; //间隔为gap的多组数据同时排    for (i = 0; i < n - gap; i++)//如果gap换成1  那就是直接插入排序    {      int end = i;      int tmp = a[end + gap];      while (end >= 0)      {        if (a[end] > tmp)        {          a[end + gap] = a[end];          end = end - gap;        }        else        {          break;        }      }      a[end + gap] = tmp;    }  }}

复制代码

3. 希尔排序的时间复杂度

gap=n , gap=gap/3+1 即 n=n/3+1 假设 x 为操作次数 3^x=n+1 x=log 3 n+1 时间复杂度为 O(log 3 N)

2.预排序会使数组接近有序 ,如 gap=1 时，就为直接插入排序，时间复杂度为 O(N)

希尔排序整体时间复杂度为 O(N *log 3 N )

三、直接选择排序

1.直接选择排序的实现


void selectsort(int arr[], int n)//直接选择排序{  int begin = 0;  int end = n - 1;  while (begin < end)  {
    int max = begin;    int min = begin;    int i = 0;    for (i = begin; i <= end; i++)    {      if (arr[i] < arr[min])      {        min = i;//通过交换找到最大值坐标      }      if (arr[i] > arr[max])      {        max = i;//通过交换找到最小值坐标      }    }    swap(&arr[begin], &arr[min]);//通过坐标将最小值交换到第begin个    if (begin == max)    {      max = min;    }    swap(&arr[end], &arr[max]);//通过坐标将最大值交换到第end个    begin++;    end--;  }}

复制代码

2.注意事项

3.直接选择排序的时间复杂度

直接选择排序 ,无论数组处于有序（最好情况下），还是无序 (最坏情况下) 都需要将整个数组遍历一遍，时间复杂度为 O(N^2)

四、堆排序

点击这里 :堆排序详解

五、冒泡排序

1.冒泡排序的实现

void bubblesort(int* a, int sz){  int i = 0;  int j = 0;  for (i = 0; i < sz - 1; i++)// i代表趟数  i在倒数第二次就已经把数组排好了   {    int exchange = 0;    for (j = 0; j < sz - 1 - i; j++)//j代表每趟的对数     {      if (a[j] > a[j + 1])      {        int tmp = 0;        tmp = a[j];        a[j] = a[j + 1];        a[j + 1] = tmp;        exchange = 1;      }    }    if (exchange == 0)//说明遍历一遍都没有进行比较，则有序    {      break;    }  }}

复制代码

2.冒泡排序的时间复杂度

正常情况下:第一趟时，共比较 n-1 次，第二趟时，共比较 n-2 次，第 n-1 趟时，共比较 1 次操作次数为: n-1+n-2+n-3+.......+1=n(n-1)/2 通过大 O 渐进法省略 ,时间复杂度为 O(N^2)

最好情况下:数组为有序时，如： 1 2 3 4 5 正好排升序，遍历一遍后发现并没有进入交换中，exchange==0 则跳出循环。时间复杂度为 O(N)

3.冒泡排序与直接插入排序谁更好？

当数组接近有序时，如： 1 2 3 5 4 61.冒泡排序:

2.直接插入排序:1 2 3 5 4 6

时间复杂度为 O(N)

则直接插入排序更优

发布于: 刚刚阅读数: 3

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

lovevivi

关注

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

还未添加个人简介

发布

暂无评论

创作场景

八大排序 (上)

一、 直接插入排序

1.概念

2.直接插入排序的实现

直接插入排序的时间复杂度

二、 希尔排序

1.概念

2. 希尔排序的实现

3. 希尔排序的时间复杂度

三、 直接选择排序

1.直接选择排序的实现

2.注意事项

3.直接选择排序的时间复杂度

四、 堆排序

五、冒泡排序

1.冒泡排序的实现

2.冒泡排序的时间复杂度

3.冒泡排序与直接插入排序谁更好？

lovevivi

评论

一、直接插入排序

二、希尔排序

三、直接选择排序

四、堆排序