【数据结构】常见的7种比较排序算法1

前端之家收集整理的这篇文章主要介绍了【数据结构】常见的7种比较排序算法1前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

● 直接插入排序(Insert Sort)

1、算法描述:

该算法是一种简单直观的是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上只需用到O(1)的额外空间的排序,因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位为最新元素提供插入空间。

2、步骤:

1)从第一个元素开始,该元素可以认为已经被排序

2)取出下一个元素,在已经排序的元素序列中从后向前扫描

3)如果该元素(已排序)大于新元素,将该元素移到下一位置

4)重复步骤3,直到找到已排序的元素小于或者等于新元素的位置

5)将新元素插入到该位置中

6)重复步骤2

插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率,但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位。

具体实现如下:

  1. voidInsertSort(int*arr,size_tsize)//直接插入排序
  2. {
  3. assert(arr);
  4. for(size_ti=0;i<size-1;++i)
  5. {
  6. intend=i;
  7. inttmp=arr[i+1];//tmp取出要插入的元素(下一个元素)
  8. while(end>=0&&arr[end]>tmp)//end要大于等于0
  9. {
  10. arr[end+1]=arr[end];//大于tmp的数后移
  11. --end;
  12. }
  13. arr[end+1]=tmp;
  14. }
  15. }

● 希尔排序(Shell Sort)

1、算法描述:

希尔排序,也称递减增量排序算法,是插入排序的一种高速而稳定的改进版本。希尔排序是基于插入排序而提出改进方法的。设置增量为gap=size/3+1,在gap不为1时,希尔排序是在进行预排序,在gap==1时,进行插入排序时,可提高效率。

1)设置增量gap为size

2)使gap=gap/3+1,同时对所有组进行插入排序,直到size-gap-1时,表示所有组已经排序完成

3)重复步骤2,直到gap为1时停止

wKioL1dBMFCRwdtYAAAgikXzSY8231.png

具体实现如下:

  1. voidShellSort(int*arr,size_tsize)//希尔排序
  2. {
  3. assert(arr);
  4. intgap=size;//gap设置插入排序区间
  5. while(gap>1)
  6. {
  7. gap=gap/3+1;//防止gap为2时,下一次gap为1,使得最后一次的gap为1
  8. //例如(254936871)使多组同时进行直接插入排序
  9. for(size_ti=0;i<size-gap;++i)
  10. {
  11. intend=i;
  12. inttmp=arr[i+gap];
  13. while(end>=0&&arr[end]>tmp)
  14. {
  15. arr[end+gap]=arr[end];
  16. end-=gap;
  17. }
  18. arr[end+gap]=tmp;
  19. }
  20. }
  21. }

● 选择排序(Select Sort)1、算法描述:

首先在未排序序列中找到最小和最大元素,存放到排序序列的两端,然后,再从剩余未排序元素中继续寻找最小和最大元素,然后放到排序序列(该序列缩短了2个元素,不包含原序列的两端)两端。以此类推,直到所有元素均排序完毕。

1)一重循环:通过i和size控制进行寻找最小和最大元素的区间

2)使min为区间的首位元素位置,max为区间的末尾元素位置

3) 二重循环:从序列中寻找最小和最大元素,注意在进行不断比较过程中进行交换,不能在找到的它们的下标后才进行交换。

具体实现如下:

  1. voidSelectSort(int*arr,size_tsize)
  2. {
  3. intmin,max;
  4. for(size_ti=0;i<size;++i,--size)
  5. {
  6. min=i;
  7. max=size-1;//max为当前选择排序段的最后一个数据
  8. //max=size-1-i时:注意不能用size进行减1,防止max=size-i-i中size的改变,重新定义len进行变化
  9. for(intj=i;j<=max;++j)
  10. {
  11. if(arr[j]<arr[min])
  12. {
  13. swap(arr[j],arr[min]);
  14. }
  15. if(arr[j]>arr[max])
  16. {
  17. swap(arr[j],arr[max]);
  18. }
  19. }
  20. }
  21. }

● 堆排序(Heap Sort)

堆积排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

升序序列的实现需要建立大堆,降序序列的实现需要建立小堆。下面对升序序列的实现进行分析。

1)大堆的建立:通过下调建立大堆,先比较左右子结点的大小,使child指向较大数,再比较父亲结点的child所指数据的大小,小于孩子结点就进行交换。

2)每次使堆的左右子树为大堆,故从下向上进行大堆的建立

3)交换堆顶元素的堆的最后一个元素,然后重新使堆(不包含最后一个元素)成为大堆

4)重复步骤3,直到堆中只有一个元素为止

具体实现如下:

  1. voidAdjustDown(int*arr,size_tparent,size_tsize)//建大堆(每次选出最大的放在后面)
  2. {
  3. size_tchild=2*parent+1;
  4. while(child<size)
  5. {
  6. if(child+1<size&&arr[child+1]>arr[child])
  7. {
  8. ++child;
  9. }
  10. if(arr[child]>arr[parent])
  11. {
  12. swap(arr[child],arr[parent]);
  13. parent=child;
  14. child=2*parent+1;
  15. }
  16. else
  17. {
  18. break;
  19. }
  20. }
  21. }
  22. voidHeapSort(int*arr,size_tsize)//升序(大堆),降序(小堆)
  23. {
  24. assert(arr);
  25. for(inti=(size-2)/2;i>=0;--i)//注意边界条件,i>=0和i=(size-2)/2
  26. {
  27. AdjustDown(arr,i,size);
  28. }
  29. for(size_ti=0;i<size;++i)
  30. {
  31. swap(arr[0],arr[size-1-i]);//交换,使大数放在堆的最后
  32. AdjustDown(arr,size-1-i);
  33. }
  34. }

● 冒泡排序(Bubble Sort)

重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误(升序的)就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换(flag==0),也就是说该数列已经排序完成。该算法是越小的元素会经由交换慢慢“浮”到数列的顶端。

1)设置标志flag。

2)从开始第一对到结尾的最后一对,比较相邻的元素。如果第一个比第二个大,就交换他们两个。

3)如果flag==0,则在进行一趟比较后没有发生交换,则序列已经有序了。

4)持续每次对越来越少的元素重复步骤2、3,总共进行了size-1趟。

具体实现如下:

  1. voidBubbleSort(int*arr,size_tsize)//冒泡排序,依次将大数据存放在后面
  2. {
  3. assert(arr);
  4. intflag=0;//标志位判断数组是否接近有序
  5. for(size_ti=0;i<size-1;++i)//进行了size-1趟冒泡
  6. {
  7. for(size_tj=0;j<size-i-1;++j)//进行比较,交换
  8. {
  9. if(arr[j]>arr[j+1])
  10. {
  11. swap(arr[j],arr[j+1]);
  12. flag=1;
  13. }
  14. }
  15. if(flag==0)//一趟结束后没有一次交换,跳出循环
  16. {
  17. break;
  18. }
  19. }
  20. }

其余比较排序算法的实现见博主的下一篇博文

猜你在找的数据结构相关文章