搜文章
推荐 原创 视频 Java开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发
Lambda在线 > 编程范 > 各种选择+冒泡+插入排序图解

各种选择+冒泡+插入排序图解

编程范 2019-11-08

排序基础算法之一,属于常见题型。下面说明一下常见的排序算法,看上哪个就用吧!


选择排序:

 
   
   
 
  1. 文字描述:对一个序列A中的元素A[1]~A[n],令i1n枚举,进行n趟操作,每趟从待排序部分【i,n】中选择最小的元素,令其与待排序部分的第一个元素A[i]进行交换,这样元素A[i]就会与当前有序区间【1,,i-1】形成新的有序区间【1,i】。于是n趟操作后,元素就会是有序的。

 
   
   
 
  1. 图形描述:



存储状态:

 
   
   
 
  1. 初始序列:{49 27 65 97 76 12 38}

  2.   1趟:1249交换:12{27 65 97 76 49 38}

  3.   2趟:27不动 :12 27{65 97 76 49 38}

  4.   3趟:6538交换:12 27 38{97 76 49 65}

  5.   4趟:9749交换:12 27 38 49{76 97 65}

  6.   5趟:7665交换:12 27 38 49 65{97 76}

  7.   6趟:9776交换:12 27 38 49 65 76 97

  8. 完成

C代码:

 
   
   
 
  1. void SelectSort(RecordType r[], int length) /*对记录数组r做简单选择排序,length为待排序记录的个数*/

  2. {

  3. int temp;

  4. for ( i=0 ; i< length-1 ; i++) //n-1趟排序

  5. {

  6. int index=i; //假设index处对应的数组元素是最小的

  7. for (int j=i+1 ; j < length ; j++)  //查找最小记录的位置

  8. if (r[j].key < r[index].key )

  9. index=j;

  10. if ( index!=i)  //若无序区第一个元素不是无序区中最小元素,则进行交换

  11. {

  12. temp = r[i];

  13. r[i] = r[index];

  14. r[index] = temp;

  15. }

  16. }

  17. }

复杂度:

 
   
   
 
  1. O(n^2)


冒泡排序:

 
   
   
 
  1. 文字描述:它是一种较简单的排序算法。它会遍历若干次要排序的数列,每次遍历时,它都会从前往后依次的比较相邻两个数的大小;如果前者比后者大,则交换它们的位置。这样,一次遍历之后,最大的元素就在数列的末尾! 采用相同的方法再次遍历时,第二大的元素就被排列在最大元素之前。重复此操作,直到整个数列都有序为止!

 
   
   
 
  1. 基本原理:

  2. 1.比较相邻的元素。如果第一个比第二个大,就交换他们两个。

  3. 2.对每一对相邻元素做同样的工作,最后的元素应该会是最大的数。

  4. 3.针对所有的元素重复以上的步骤,除了最后一个。

  5. 4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

 
   
   
 
  1. 图片描述:

各种选择+冒泡+插入排序图解

C代码:

 
   
   
 
  1. void bubbleSort (elemType arr[], int len) {

  2. elemType temp;

  3. int i, j;

  4. for (i=0; i<len-1; i++) //外循环为排序趟数,len个数进行len-1趟

  5. for (j=0; j<len-1-i; j++) { // 内循环为每趟比较的次数,第i趟比较len-i次

  6. if (arr[j] > arr[j+1]) { // 相邻元素比较,若逆序则交换(升序为左大于右,降序反之)

  7. temp = arr[j];

  8. arr[j] = arr[j+1];

  9. arr[j+1] = temp;

  10. }

  11. }

  12. }

算法复杂度:

 
   
   
 
  1. O(N^2)


直接插入排序:

 
   
   
 
  1. 文字描述过程:

  2. 1趟插入:将第2个元素插入前面的有序子序列,此时前面只有一个元素,当然是有序的

  3. 2趟比较:将第3个元素插入前面的有序子序列,前面的2个元素是有序的

  4. ......

  5. n-1趟比较:将第n个元素插入前面的有序子序列,前面n-1个元素是有序的

 
   
   
 
  1. 图片描述(第一种):

 
   
   
 
  1. 图片描述(第二种):


java代码:

 
   
   
 
  1. public static void insertionSort(int[] nums) {

  2. int temp;

  3. for(int i = 1; i < nums.length; i++) {

  4. for(int j = i - 1; j >= 0 && nums[j] > nums[j + 1]; j--) {

  5. temp = nums[j];

  6. nums[j] = nums[j + 1];

  7. nums[j + 1] = temp;

  8. }

  9. }

  10. }

复杂度:

 
   
   
 
  1. O(n^2)

优化:

 
   
   
 
  1. 上面的算法的缺点:在第i-1趟插入时,需要把第i个元素插入到前面的i-1个元素中,该算法总是从i-1个元素开始逐个比较之前的每个元素,直到找到第i个元素的插入位置,这显然没有利用前面0~i-1个元素已经有序的特点。


  2. 优化:在0~i-1个有序元素给第i个元素寻找插入的位置时,使用二分查找法可以有效提高查找插入位置的时间效率,经过优化的插入排序称为折半插入排序


折半插入排序:

Java代码:

 
   
   
 
  1. public static void binaryInsertionSort(int[] nums) {

  2. for(int i = 1; i < nums.length; i++) {

  3. int left = 0;

  4. int right = i - 1;

  5. int temp = nums[i];

  6. // 通过二分查找找到插入的位置

  7. while(left <= right) {

  8. int mid = (left + right) / 2;

  9. if(temp > nums[mid]) {

  10. left = mid + 1;

  11. } else {

  12. right = mid - 1;

  13. }

  14. }

  15. // 插入位置之后的元素依次向后移动

  16. for(int j = i; j > left; j--) {

  17. nums[j] = nums[j - 1];

  18. }

  19. // 更新插入位置的值

  20. nums[left] = temp;

  21. }

  22. }


由于排序题中大部分都只需要得到排序的最终结果,而不需要写排序的完整过程(例如冒泡排序,快速排序等过程)因此比赛时强烈建议使用C语言中的库函数qsort或是C++中的sort函数,接下来主讲更简洁的sort函数
1.如何使用sort排序

 
   
   
 
  1. 1.函数的使用必须加上头文件#include<algorithm> using namespace std;

  2. 3.通常是sort(a,a+len,cmp())

  3. 不写比较函数的话,默认从小到大排序

  4. 4.通常与vector容器配合使用(想了解的请点击如下链接)

参考:1044题-[编程拓展]三个字符串的排序-题解(STL—-vector+sort)

2.cmp()实现
(1)从大到小

 
   
   
 
  1. bool cmp(int a,int b){

  2. return a>b;

  3. }

(2)结构体数组从小到大(一级排序)

 
   
   
 
  1. struct node{

  2. int x;

  3. };

  4. bool cmp(node a,node b){

  5. return a.x<b.x;

  6. }

(3)结构体数组,先按x从小到大,若x相等,则按y从大到小(二级排序)

 
   
   
 
  1. struct node{

  2. int x;

  3. int y;

  4. };

  5. bool cmp(node a,node b){

  6. if(a.x!=b.x) return a.x<b.x;

  7. else return a.y>b.y;

  8. }

(4)结构体里的字符数组,先按x(字典序)从小到大,若x相等,则按y(字典序)从大到小(二级排序)

 
   
   
 
  1. struct node{

  2. char x[100];

  3. char y[100];

  4. };

  5. bool cmp(node a,node b){

  6. if(a.x!=b.x) return strcmp(a.x,b.x)<0;

  7. else return strcmp(a.y,b.y)>0;

  8. }

=================还有很多排序 TT==================

2019-06-21 补充了一个结构体里的字符数组的(字典序)比较
===============有时间继续研究更新==================

写了很久,赠人玫瑰,手有余香。点个赞吧。^-^


点击原文查看作者原文哦

版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《各种选择+冒泡+插入排序图解》的版权归原作者「编程范」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注编程范微信公众号

编程范微信公众号:dotcpp

编程范

手机扫描上方二维码即可关注编程范微信公众号

编程范最新文章

精品公众号随机推荐

下一篇 >>

插入排序java