1、快速排序
快速排序是冒泡排序的改进版，也是最好的一种内排序，在很多面试题中都会出现，也是作为程序员必须掌握的一种排序方法。
基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列
1.1 原理
在要排的数（比如数组A）中选择一个中心值key（比如A[0]），通过一趟排序将数组A分成两部分，其中以key为中心，key右边都比key大，key左边的都key小，然后对这两部分分别重复这个过程，直到整个有序。
整个快排的过程就简化为了一趟排序的过程，然后递归调用就行了。
假设要排的数组为：A[8] ={ 5 2 8 9 2 3 4 9 }，选择 key = 5， 开始时 i=0，j=7（升序排序）
1，定义i=0，j=A.lenght-1，i为第一个数的下标，j为最后一个数下标
2，从数组的最后一个数Aj从右往左找，找到第一小于key的数，记为Aj；
3，从数组的第一个数Ai 从左往右找，找到第一个大于key的数，记为Ai；
4，交换Ai 和Aj
5，重复这个过程，直到 i=j
6，调整key的位置，把A[i] 和key交换
1.2 时间复杂度
快排在最糟糕得情况下时间复杂度是O(n²)，平均的复杂度是O(nlogn)
1.3 代码
public class QuickSort {
private static int count;
/**
* 测试
* @param args
*/
public static void main(String[] args) {
int[] num = {3,45,78,64,52,11,64,55,99,11,18};
System.out.println(arrayToString(num,"未排序"));
QuickSort(num,0,num.length-1);
System.out.println(arrayToString(num,"排序"));
System.out.println("数组个数："+num.length);
System.out.println("循环次数："+count);
}
/**
* 快速排序
* @param num 排序的数组
* @param left 数组的前针
* @param right 数组后针
*/
private static void QuickSort(int[] num, int left, int right) {
//如果left等于right，即数组只有一个元素，直接返回
if(left>=right) {
return;
}
//设置最左边的元素为基准值
int key=num[left];
//数组中比key小的放在左边，比key大的放在右边，key值下标为i
int i=left;
int j=right;
while(i<j){
//j向左移，直到遇到比key小的值
while(num[j]>=key && i<j){
j--;
}
//i向右移，直到遇到比key大的值
while(num[i]<=key && i<j){
i++;
}
//i和j指向的元素交换
if(i<j){
int temp=num[i];
num[i]=num[j];
num[j]=temp;
}
}
num[left]=num[i];
num[i]=key;
count++;
QuickSort(num,left,i-1);
QuickSort(num,i+1,right);
}
/**
* 将一个int类型数组转化为字符串
* @param arr
* @param flag
* @return
*/
private static String arrayToString(int[] arr,String flag) {
String str = "数组为("+flag+")：";
for(int a : arr) {
str += a + "\t";
}
return str;
}
}
2、归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
2.1 特点：
- 时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlogn)
- 辅助空间复杂度为O(n)
- 稳定
- 顺序存储与链表存储均可
2.2 原理
分而治之(divide - conquer);每个递归过程涉及三个步骤
分解: 把待排序的 n 个元素的序列分解成两个子序列, 每个子序列包括 n/2 个元素.
治理: 对每个子序列分别调用归并排序MergeSort, 进行递归操作
合并: 合并两个排好序的子序列,生成排序结果.
2.3 时间复杂度
在最坏、最佳、平均情况下归并排序时间复杂度均为o(nlogn)，从合并过程中可以看出合并排序稳定。
2.4 代码
public class MergeSort {
/**
* 归并排序递归实现
* @param a
* @param left
* @param right
*/
public void mergeSort(int[] a,int left,int right){
if(left<right){
int middle = (left+right)/2;//分解
mergeSort(a, left, middle);//治理
mergeSort(a,middle+1,right);
merge(a,left,middle,right);//合并
}
}
/**
* 合并
* @param a
* @param left
* @param middle
* @param right
*/
private void merge(int[] a, int left, int middle, int right) {
int [] tmpArray = new int[a.length];
int rightStart = middle+1;
int tmp = left;
int third = left;
//比较两个小数组相应下标位置的数组大小，小的先放进新数组
while(left<=middle&&rightStart<=right){
if(a[left]<=a[rightStart]){
tmpArray[third++] = a [left++];
}else{
tmpArray[third++] = a[rightStart++];
}
}
//如果左边还有数据需要拷贝，把左边数组剩下的拷贝到新数组
while(left<=middle){
tmpArray[third++] = a[left++];
}
//如果右边还有数据......
while(rightStart<=right){
tmpArray[third++] = a[rightStart++];
}
while(tmp<=right){
a[tmp] = tmpArray[tmp++];
}
}
public static void main(String[] args){
MergeSort mergeSort = new MergeSort();
int [] a = new int[]{90,3,2,67,44,-9,87,65,11,9,2,8};
mergeSort.mergeSort(a, 0, a.length-1);
for(int n:a){
System.out.print(" "+n);
}
}
}
归并算法是分治思想的经典应用，其基本思想就是将两个有序的表合并成为一个有序表。如果a数组是有序的，b数组也是有序的，则最后合并后，c数组也是有序的
//实现将a、b两个数组合并到c数组
public void merge(int a[], int b[], int[] c) {
int aIndex=0, bIndex=0, cIndex=0;
int aEnd=a.length, bEnd=b.length;
c=new int[aEnd+bEnd];
while (aIndex<=aEnd && bIndex<=bEnd) {
if (a[aIndex]<b[bIndex]) {
c[cIndex++]=a[aIndex++];
} else {
c[cIndex++]=b[bIndex++];
}
}
while (aIndex<=aEnd) {
c[cIndex++]=a[aIndex++];
}
while (bIndex<=bEnd) {
c[cIndex++]=b[bIndex++];
}
}
归并排序就是在这个合并有序数组的例子上继续扩展，先把待排序数组多次分解成两个子数组，分解到最后，每个子数组都只有一个值，这样的话每个子数组就是有序的，然后就可以调用上面的合并有序数组的例子了。
