常⻅排序算法效率⽐较

各种排序最好最坏的比较次数

https://blog.csdn.net/u013176681/article/details/41786263

排序算法——稳定性、比较次数、交换次数

https://blog.csdn.net/derhasebruder/article/details/78388637

冒泡排序：

 

冒泡排序

https://blog.csdn.net/kelinfeng16/article/details/84034386

原文地址：https://github.com/hustcc/JS-Sorting-Algorithm/blob/master/2.selectionSort.md

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

作为最简单的排序算法之一，冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样，每次都在第一页第一位，所以最熟悉。冒泡排序还有一种优化算法，就是立一个 flag，当在一趟序列遍历中元素没有发生交换，则证明该序列已经有序。但这种改进对于提升性能来

说并没有什么太大作用。

1. 算法步骤

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

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。

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

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

https://blog.csdn.net/lu_1079776757/article/details/80459370

 

 

解释说明一下 为什么进行了 N-i-1次  

冒泡排序就是把最大（最小）的放在前（后）面，那么后面的数据肯定已经排好了，不用再比较了，循环一次，排好一个数，那么再次循环的时候就把需要比较的长度-1，也就是-i。 如： 原数987654321 第一次876543219 比较次数9-1-0 两两比较，全部比 第二次765432189 这时候比较的次数是9-1-1，最后一个不用比 三，654321789 次数9-1-2 89不用比 ... ...

 

#include<stdio.h> #define N 8 int main() { int i,j,k,t; int a[N]={99,1,3,6,22,11,56,31}; for(i=1;i<N;i++)// 控制循环次数，执行七次循环; { for(j=0;j<N-1;j++) //1.i=0;i<N-1; 2.i=1;i<N;因为每一次是用相邻两个元素比较，所以就是n-1次。 { if(a[j]>a[j+1])//比较前后两数大小，替换 { t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } } for(j=0;j<N;j++)//输出 a[0]-a[7] printf("%d ",a[j]); printf("\n"); } #include<stdio.h> #define N 8 int main() { int i,j,k,t; int a[N]={99,1,3,6,22,11,56,31}; for(i=0;i<N-1;i++)// i=1;i<N;i++ 遍历次数，N-1次 { for(j=0;j<N-i-1;j++) //元素下标 a[0]-a[7] { if(a[j]>a[j+1])//比较前后两数大小，替换 { t=a[j]; a[j]=a[j+1]; a[j+1]=t; } } } for(j=0;j<N;j++)//输出 a[0]-a[7] printf("%d ",a[j]); printf("\n"); }

 

 选择排序

https://blog.csdn.net/kelinfeng16/article/details/84073496 ☆

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

https://www.cnblogs.com/antusheng/p/10313347.html

1. 算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。

再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

重复第二步，直到所有元素均排序完毕。

 

 

 

 

#include<stdio.h> #define N 8 int main() { int i,j,imax,t; int a[N]={36,1,3,6,89,101,56,31}; for(i=0;i<N-1;i++)// i=1;i<N;i++ 遍历次数，N-1次 { imax=i;//令i为最大值 for(j=i+1;j<N;j++) { if(a[j]>a[imax]) imax=j; } t=a[i]; a[i]=a[imax]; a[imax]=t; } for(j=0;j<N;j++)//输出 a[0]-a[7] printf("%d ",a[j]); printf("\n"); }

二分查找法

仅当列表有序的时候，二分查找才管用!！

https://blog.csdn.net/qq_42739440/article/details/96860023

【算法图解】 之 [二分查找法] 详解

https://blog.csdn.net/lan410812571/article/details/88120166

算法探索实录 - 1、二分查找算法

二分查找算法优点：

查找次数较少查找速度快平均性能好

 

二分查找算法缺点：

要求列表为有序列表插入删除困难不适用于经常变动的数据列表

 

 

#include<stdio.h> #define N 8 int main() { int i,j,index,t,x,low,high,mid,n=0; int a[N]={36,1,3,6,89,101,56,31}; for(i=0;i<N-1;i++)// i=1;i<N;i++ 遍历次数，N-1次 { index=i;//令i为最大值 for(j=i+1;j<N;j++) { if(a[j]>a[index]) index=j; } t=a[i]; a[i]=a[index]; a[index]=t; } for(j=0;j<N;j++)//输出 a[0]-a[7] printf("%d ",a[j]); printf("\n"); printf("请输入你要查找的数："); scanf("%d",&x); low=0; high=N-1; while(low<=high) { mid=(low+high)/2; if(x==a[mid]) break; else if (x>a[mid]) high=mid-1; else low=mid+1; } if(low<=high) { printf("%d was found!\n",x); } else printf("%d was not found!\n",x); }