排序算法整理
1、快速排序
快速排序基于分治思想,相比于冒泡排序中每一轮只将一个元素移动到最右边,快速排序每轮会选出一个基准元素,并将数组中比他大的数移动到右边(从小到大排序),比它小的数移动到左边,从而将元素分割成两个部分,下一轮再分别在这两部分进行同样的操作。
假设数组中有n个元素,在每一轮中,数组中的全部元素都将被遍历、比较、交换一遍,时间复杂度是O(n)。但由于分而治之,平均情况下只会进行O(logn)轮,因此快速排序算法的整体平均时间复杂度为O(nlogn)。
下面给出代码:
public class Quick {
public static void main(String[] args) {
QuickSort sort = new QuickSort();
int [] arrays = new int[]{-1,0,3,5,7,9,6,3,4,5,12,8,6,5};
sort.quickSort(arrays,0,arrays.length-1);
System.out.println(Arrays.toString(arrays));
}
}
class QuickSort{
public void quickSort(int[]arrs,int startIndex,int endIndex){
//跳出递归
if(startIndex >= endIndex){
return;
}
int pivot = sort(arrs,startIndex,endIndex);//取基准元素值
quickSort(arrs,startIndex,pivot-1);//左区间递归
quickSort(arrs,pivot+1,endIndex);//右区间递归
}
//双边循环法,返回pivot的位置
public int sort(int[] arrs,int startIndex,int endIndex){
//选第一个作为基准元素,当第一个作为基准元素时,如果恰好是最大值或最小值,会导致分治法失效,
//因为这种情况下无法将数组分成两个子数组,算法时间复杂度会退化成O(n2)。这里也可以在区间内随机一个数,作为基准元素
int pivot = arrs[startIndex];
int left = startIndex;
int right = endIndex;
while (left!=right){
while (left<right&&arrs[right]> pivot)right--;
while (left<right&&arrs[left] <= pivot)left++;
//交换左右两边的元素
if(left<right){
int l = arrs[left];
arrs[left] = arrs[right];
arrs[right] = l;
}
}
if(left == right){
arrs[startIndex] = arrs[left];
arrs[left] = pivot;
}
return left;
}
}
上面用的是双边循环法,在每个区间中利用首尾两个指针向中间逼近的方式,找到基准元素所在的位置。(说起来这种方式和三数之和中用到的双指针法蛮像的==)但这种方式虽然很直观,但代码量比较大,一个循环套两个循环有点令人头晕,因此还可以使用单边循环法,按照顺序遍历一遍,通过一个指针标识较小值区间和较大值区间的边界,达到分治的效果。
下面是单边循环法的实现:
//单边循环法,返回pivot的位置
public int sort1(int[] arrs,int startIndex,int endIndex){
//选第一个作为基准元素,当第一个作为基准元素时,如果恰好是最大值或最小值,会导致分治法失效,
//因为这种情况下无法将数组分成两个子数组,算法时间复杂度会退化成O(n2)
int pivot = arrs[startIndex];
int mark = startIndex;
for (int i = startIndex;i<=endIndex;i++) {
int val = arrs[i];
if(val < pivot){
mark++;//如果遍历值小于标准值,向右移动mark,较小值区间+1
int p = arrs[mark];//交换该值与mark指向的值的位置
arrs[mark] = val;
arrs[i] = p;
}
}
//交换mark指向的位置和pivot的位置
arrs[startIndex] = arrs[mark];
arrs[mark] = pivot;
return mark;
}
看,只要一个大循环就完事了,简明扼要(