排序算法整理
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;
}
看，只要一个大循环就完事了，简明扼要（
