第七章排序算法法法

算法时间复杂度

衡量一个算法的时间复杂度

度量一个程序(算法)执行时间的两种方法

事后统计法

这种方法可行,但是有两个问题:一是要想对涉及的算法的运行性能进行评测,需要实际运行该程序;二是所得时间的统计量依赖于计算机的硬件,软件等环境因素,这种方式,要在同一台计算机的相同状态下运行,才能比较哪个算法更快
事前估算方法

通过分析某个算法的时间复杂度来判断哪个算法更优

时间频度

基本介绍:一个算法花费的时间与算法中语句执行的次数成正比例,哪个算法中语句执行次数多,它花费的时间就多 一个算法中语句执行次数称为语句频度或时间频度记为T(n)

原本时间复杂度为T(n)=n+1,将原计算式子变成公式,就可以变成1

常见的时间复杂度

1.冒泡排序

基本介绍:冒泡排序的基本思想是:通过对待排序序列从前向后(从下标较小的元素开始),依次比较相邻元素的值,若发现逆序的交换,使值较大的元素逐渐从前移向后部,就像水底下的气泡一样逐渐向上冒

因为排序的过程中,各元素不断接近自己的位置,如果一趟下来没有进行交换,就说明序列有序,因此要在排序过程中设置一个flag判断元素是否进行过交换从而减少不必要的比较(这里说的是优化,可以在冒泡排序写好后,在进行)

冒泡排序应用实例

import java.util.Arrays;public class Main {public static void main(String[] args) {int[]arr= {1,4,2,3};bubbleSort(arr);System.out.println(Arrays.toString(arr));}public static void bubbleSort(int[] arr){boolean flag=false;//设置一个flag表示第几轮循环中有没有完全不用调整的for (int i = 0; i < arr.length-1; i++) {for (int j = i; j <arr.length-1-i ; j++) {if(arr[j]>arr[j+1]){flag=true;int temp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}System.out.println("第"+(i+1)+"轮排序"+ Arrays.toString(arr));if(!flag){break;}else {flag=false;}}}
}

冒泡排序的最坏时间复杂度为 O(n2)。

平均时间复杂度也是 (O(n^2))。

最好情况下达到 (O(n)) 的时间复杂度。

2.选择排序

选择式排序也属于内部排序法,是从欲排序的数据中,按照指定规则选出某一元素,再依规则交换位置后达到排序的目的

public static void selectSort(int[] arr) {for (int i = 0; i < arr.length - 1; i++) {int min = arr[i];//假设i为最小的数int index = i;//索引for (int j = i + 1; j < arr.length; j++) {if (arr[j] < min) {min = arr[j];//发现比min小的数,让min变成这个数index = j;//index去记录小的数的索引}}if (index != i) {//如果需要交换,比较的数和比他小的数进行交换arr[index] = arr[i];arr[i] = min;}}}

选择排序的最坏时间复杂度为 (O(n^2))。

所以其平均时间复杂度也是 (O(n^2))。

最好时间复杂度同样为 (O(n^2))。

3.插入排序

插入式排序属于内部排序法,是对于欲排序的元素以插入的方式找寻该元素的适当位置,以达到排序的目的

public static void insertSort(int[] arr) {for (int i = 1; i < arr.length; i++) {int temp = arr[i];//用temp拿到要和前面已经排序号的数进行比较int index = i - 1;//拿到比较好的数最大的索引while(index>=0&&temp<arr[index]){//当temp小于index索引的数arr[index+1] = arr[index];//让要比较的数索引位置变成大于他的数index--;//接着比较下一个}if(index+1!=i){arr[index+1] = temp;//循环结束表示index的数比temp小,让index+1变成temp}}}

插入排序的最好时间复杂度为 (O(n))，

平均时间复杂度为 (O(n^2))。

最坏时间复杂度为 (O(n^2))。

插入排序在处理小规模数据或者基本有序的数据时表现较好

4.快速排序

是对冒泡排序的一种改进基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后按找此方法对这两部分数据分别进行快速排序,这个过程可以递归进行,以达到整个数据变成有序序列

public static void quickSort(int[] arr,int left,int right) {int l=left;//表示左边界int r=right;//表示右边界int mid=(l+r)/2;//中间元素索引int pivot=arr[mid];//分区操作while(l<r) {while(arr[l]<pivot) {l++;}while (arr[r]>pivot) {r--;}if(l==r){break;}//当左边大于中间值同时右边小于中间值,交换左右两个值int temp=arr[l];arr[l]=arr[r];arr[r]=temp;if(pivot==arr[l]){//如果标准值==左边边界值,表示交换完成一次右边比较过了,右边减一缩小范围下面同理r--;}if(pivot==arr[r]){l++;}}if(l==r){//l=r需要重置否则下面不会继续执行l++;r--;}if(left<r){//当最左边边界值小于要排序的右边边界值quickSort(arr,left,r);}if(right>l){//当最右边边界值大于要排序的左边边界值quickSort(arr,l,right);}}

最好情况时间复杂度为 (O(nlogn))。

最坏情况时间复杂度为 (O(n^2))。

平均情况 (O(nlogn))

5.希尔排序

代码实现交换式:

 public static void shellSort(int[] arr) {int len = arr.length;// 外层循环控制增量 gap 的变化，初始值为数组长度的一半，每次循环将 gap 缩小一半，直到 gap 为 0for (int gap = len / 2; gap > 0; gap /= 2) {// 中层循环从 gap 位置开始，对每个子序列进行插入排序for (int i = gap; i < len; i++) {// 内层循环用于比较和交换子序列中的元素int j = i;while (j - gap >= 0 && arr[j] < arr[j - gap]) {//j-gap>0时表示还可以向前比较(向前移动gap还有数)// 交换 arr[j] 和 arr[j - gap] 的值int temp = arr[j];arr[j] = arr[j - gap];arr[j - gap] = temp;// j 减去 gap，继续在子序列中向前比较j -= gap;}}}}

代码实现移动式:

public static void shellSort(int[] arr) {int len = arr.length;// 外层循环控制增量 gap 的变化，初始值为数组长度的一半，每次循环将 gap 缩小一半，直到 gap 为 0for (int gap = len / 2; gap > 0; gap /= 2) {// 中层循环从 gap 位置开始，对每个子序列进行插入排序for (int i = gap; i < len; i++) {int temp = arr[i];//获取当前要插入的值int j=i;//得到索引while(j-gap>=0&&arr[j-gap]>temp) {//当间隔gap的前面还有数字并且比temp小arr[j] = arr[j-gap];//让此时变成前面比他大的j-=gap;//让j变成那个数}arr[j]=temp;//最后退出循环即是temp应该插入的位置}}}

交换式实现简单易懂，但效率较低；移动式实现虽然逻辑稍复杂，但效率更高，在实际应用中通常更推荐使用移动式实现。

网上是这么说,但是就本人而言第二种更好理解

简单插入排序存在问题当最小的在最后面,后移次数明显增多

6.归并排序

利用归并的思想实现的排序方法,该算法采用经典的分治策略成一些小的问题然后求解,而治的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之

import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {int []arr={12,32,22,10};int []temp=new int[arr.length];//临时数组mergeSort(arr,0, arr.length-1, temp);//0 3System.out.println(Arrays.toString(arr));}//分+合方法public static void mergeSort(int[]arr,int left,int right,int[]temp){if(left<right){int mid=(right+left)/2;//中间索引mergeSort(arr,left,mid,temp);//向左递归进行分解mergeSort(arr,mid+1,right,temp);//向右递归进行分解merge(arr,left,mid,right,temp);//到合并时}}//合并方法public static void merge(int[]arr,int left,int mid,int right,int[]temp){int i=left;//初始化i,左边有序序列初始索引int j=mid+1;//初始化j 右边有序序列初始索引int t=0;//指向temp数组的当前索引//while (i<=mid&&j<=right){//if(arr[i]<=arr[j]){//左边有序序列当前元素小于等于右边有序序列当前元素//即将左边元素调整到temp数组temp[t]=arr[i];//小的放在t的最小索引上i+=1;//i和t向前移动 1t+=1;//1}else {temp[t]=arr[j];j+=1;//2t+=1;//2}}// 把剩余数据的一遍数据依次全部填充到tempwhile (i<=mid){temp[t]=arr[i];i+=1;t+=1;}//把剩余数据依次填充while (j<=right){temp[t]=arr[j];j+=1;t+=1;}//将temp数组拷贝到arr中t=0;int tempLeft=left;while (tempLeft<=right){arr[tempLeft]=temp[t];t+=1;tempLeft+=1;}}
}

归并排序的时间复杂度是 (O(n log n))，这使得它在处理大规模数据时具有较高的效率。同时，它也是一种稳定的算法>排序算法，即相等元素的相对顺序在排序前后保持不变。

6.基数排序

import java.util.Arrays;public class Main {public static void main(String[] args) {int[]arr={1111111111,2,3,51111,1111};radixSort(arr);System.out.println(Arrays.toString(arr));}public static void radixSort(int []arr){//定义桶 一个二维数组表示10个桶//1.为了防止放入数的时候,数据溢出,则每一个一维数组,大小定位arr.length//2.名明确,基数排序是使用空间换时间的经典算法int[][]bucket=new int[10][arr.length];//记录每个桶中的数据个数,实际存放了多少个数据,我们定义一个一维数组来记录各个桶//的每次放入的数据个数//可以这里理解//比如:bucketElementCounts[0],记录的就是bucket[0]桶的放入数据个数int[]bucketElementCounts=new int[10];//求出最大的数int maxSize=arr[0];for (int i = 1; i <arr.length ; i++) {if(maxSize<arr[i]){maxSize=arr[i];}}int length = ("" + maxSize).length();//求出最大的数的位置for (int k = 0,n=1; k <length ; k++,n*=10) {//k表示第几位数for (int i = 0; i <arr.length ; i++) {//遍历数组中的每一个数字int digitOfElement=arr[i]/n%10;//取出数组中每个数字的个位数字bucket[digitOfElement][bucketElementCounts[digitOfElement]]=arr[i];//由上面个位数字得出应该放在第几个桶,并且在对应的位置上将数字放上去bucketElementCounts[digitOfElement]++;//由于在该位置放了个数要+1}//次循环遍历之后个位小的数会出现在考前的桶,个位数相同的数在同一个桶中int index=0;for (int i = 0; i <bucket.length ; i++) {//分别遍历10个桶if(bucketElementCounts[i]!=0){//如果不为0证明该个位有数for (int j = 0; j <bucketElementCounts[i]; j++) {//将所有数遍历出来放回原数组arr[index]=bucket[i][j];index++;}bucketElementCounts[i]=0;//重新将该数设置为0 }}//在进入k的2的循环就是遍历十位}}
}