基本排序方法的优化

前几天面试的时候被问到了选择排序的优化方法，之前只知道三种快排，四种优化，没有研究过选择排序的优化。今天通过这篇博客总结一下，几种基本排序（冒泡排序，选择排序，插入排序）的优化方法。

冒泡排序的优化 下面这个是最常见的冒泡排序的写法： 每次将最大的数冒泡到顶部，时间复杂度为O（n**2）

public void bubble_sort(int[] a,int n) { for(int i=0;i<n;i++) for(int j = 1;j<n-i;j++) { if(a[j-1]>a[j]){ int temp=a[j-1]; a[j-1]=a[j]; a[j]=temp; } } }

那么如何对冒泡排序的时间复杂度进行优化呢？ 既然要进行优化，就要从冒泡排序的复杂性开始讨论。 例如数组{3，2，4，5，6}。经过第一轮排序其实就已经有序了，但是冒泡排序还会进行接下来的几轮排序。所以可以从这个点上进行优化，检验是否数组已经有序，保证不进行无调整的排序。 下面是优化版的代码

public void bubbleSort_plus(int[] arr){ boolean flag=true; for(int i=0;i<arr.length-1&&flag;i++){ flag=false; for(int j=arr.length-1;j>i;j--){ if(arr[j]<arr[j-1]){ flag=true; int tmp=arr[j]; arr[j]=arr[j-1]; arr[j-1]=tmp; } } } }

利用boolean定义一个flag变量，用来检查已完成的排序是否已经有序，如果有序，flag不会被赋值为true，下次不会再进入循环，可以省略掉多余的排序次数。 选择排序的优化 下面是传统的选择排序，每次从要排序数组中选出最小的值，每经过1轮排序，将这一轮的最小值min与parr[i]换位。将要排序数组向前移动一位。 时间复杂度O（n**2）

public void SelectSort(int[] arr)//选择排序（升序） { int size=arr.length; for (int i = 0; i < size; i++){ int min = parr [i]; for (int j = i + 1; j < size; j++){ if (parr [j]<min){ int temp=min; min=parr[j]; parr[j]=temp; } } if (min!=parr [i]) { int temp1=min; min=parr[i]; parr[i]=temp1; } } }

下面是选择排序的优化算法 思考算法的优化就要思考有哪里可以优化，选择排序是选出没次排序数组中的最小值，以达到排序的目的，那么既然可以选择每次排序的最小值，是不是也可以找出每次排序的最大值，那么，一次就确定了两个位置，就大大地提升了排序的效率。优化后的选择排序时间复杂度为O（n*logn） 下面是代码

public void SelectSort(int[] parr)//选择排序（优化方案）{ int size=parr.length; int left; int right; int temp; for (left = 0,right = size - 1; left < right; left++, right--；{ int min = parr[left]; int max = parr[right]; for (int i = left+1; i <= right; i++)//遍历找出最大和最小元素{ if (min>parr[i]) { temp=min; min=parr[i]; parr[i]=temp; } else if (parr[i] > max) { temp=max; max=parr[i]; parr[i]=temp; } } if (min != parr[left]){ temp=min; min=parr[left]; parr[left]=temp; if (max == parr[left]){ max = min; } } if (max != parr[right]){ temp=max; max=parr[right]; parr[right]==temp; if (min == parr[right]){ min = max; } } } }

插入排序的优化 关于插入排序，算法导论上有一个很形象的例子，比如斗地主的摸牌阶段，你每摸一张牌，就是从左往右，或者从右往左，找到适合它大小的位置插入，这就是一个插入排序的过程。 所以当进行完了第n轮排序，会保证前n个数有序。（从左向右插入的情况） 时间复杂度O（n**2） 以下是代码：

public void insertSort3(int a[]) { int i; int tmp; int j; int len=a.length; for (i = 1; i < len; i ++) for(j = i; j > 0 && a[j - 1] > a[j]; j--) { tmp = a[j - 1]; a[j - 1] = a[j]; a[j] = tmp; } }

要想优化插入排序，也首先从过程开始分析，像一个有序数组中找到一个合适的位置，插入一个新的元素，插入排序中实现这个目的是遍历，所以时间复杂度较高，那么有序数组中找到合适位置，是不是会想到二分查找呢。所以有了优化的方案。 通过二分查找，以logn的时间复杂度可以找到需要插入的位置，优化后的插入排序的时间复杂度为O（n*logn） 以下是代码

public static void insertSort2(int[] a) { for (int i = 0; i < a.length-1; i++) { int temp=a[i+1]; int low=0; int high=i; int mid; //在low和high之间的区域进行二分查找，找到新插入的元素位置 while(low<=high){ mid=(low+high)/2; if(a[mid]>temp){ high=mid-1; }else{ low=mid+1; } } //经过上面的二分查找，得到新元素的位置是：high+1 //把[high+1,i]区间内的所有元素往后移一个位置 for (int j = i; j > high; j--) { a[j+1]=a[j]; } a[high+1]=temp; } }

总结了三种最基本的排序算法的优化，想说一下，自己对优化算法的理解。要想优化一个算法，首先要细化算法的实现，找出其中复杂的地方，用更简单的方法去实现。当然这些东西说起来比较简单，实现起来需要很多经验的积累。优化不光是时间复杂度，空间复杂度，包括很多处理上都可以尝试去优化。总之，算法的坑还是很深的，关于算法优化的例子，我以后还会继续总结的。