各类排序算法
排序算法一般分类：
冒泡排序
原理
比较两个相邻的元素，将值大的元素交换至右端。
思路
依次比较两个相邻的数，将小数放到前面，大数放到后面
即在第一趟：首先比较第1个数和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此一直继续下去，直到比较最后两个数，将小数放前，大数放后。然后重复第一趟步骤，直到所有排序完成。
第一趟比较完成后，最后一个数一定是数组中最大的一个数，所以第二趟比较的时候最后一个数不参与比较。
第二趟完成后，倒数第二个数也一定是数组中第二大的数，所以第三趟比较的时候最后两个数不参与比较。
依次类推......
代码实现
public class BubbleSort {
public static void main(String[] args) {
int[] array = {2,4,1,5,67,2,45,78,3,9};
bubbleSort(array);
}
public static void bubbleSort(int[] array){
for(int i = 0 ; i < array.length-1; i++){
for(int j = 0 ; j < array.length-1; j++){
if(array[j] > array[j+1]){
int temp = array[j+1];
array[j+1] = array[j];
array[j] = temp;
}
}
}
System.out.println("排序后的数组为:" + Arrays.toString(array));
}
}
输出结果：
排序后的数组为: [1, 2, 2, 3, 4, 5, 9, 45, 67, 78]
特点分析
冒泡排序的优点：每进行一趟排序，就会少比较一次，因为每进行一趟排序都会找出一个较大值。如上例：第一趟比较之后，排在最后的一个数一定是最大的一个数，第二趟排序的时候，只需要比较除了最后一个数以外的其他的数，同样也能找出一个最大的数排在参与第二趟比较的数后面，第三趟比较的时候，只需要比较除了最后两个数以外的其他的数，以此类推……也就是说，没进行一趟比较，每一趟少比较一次，一定程度上减少了算法的量。
用时间复杂度来说：
- 如果我们的数据正序，只需要走一趟即可完成排序。所需的比较次数C和记录移动次数M均达到最小值，即：Cmin=n-1;Mmin=0;所以，冒泡排序最好的时间复杂度为
O(n)。 - 如果很不幸我们的数据是反序的，则需要进行
n-1趟排序。每趟排序要进行n-i次比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值。
- 冒泡排序的最坏时间复杂度为：O(n^2)
- 冒泡排序的最好时间复杂夫为：O(n)
- 冒泡排序的平均时间复杂度：O(n)
- 冒泡排序是一种稳定的排序算法
快速排序
原理
从一个数组中随机选出一个数N，通过一趟排序将数组分割成三个部分，1、小于N的区域 2、等于N的区域 3、大于N的区域，然后再按照此方法对小于区的和大于区分别递归进行，从而达到整个数据变成有序数组。
思路
如下图：
假设最开始的基准数据为数组的第一个元素23，则首先用一个临时变量去存储基准数据，即tmp=23，然后分别从数组的两端扫描数组，设两个指示标志：low指向起始位置，high指向末尾。
首先从后半部分开始，如果扫描到的值大于基准数据就让high-1，如果发现有元素比该基准数据的值小，比如上面的18 <= tmp，就让high位置的值赋值给low位置，结果如下：
然后开始从前往后扫描，如果扫描到的值小于基准数据就让low+1，如果发现有元素大于基准数据的值，比如上图46 >= tmp，就再将low位置的值赋值给high位置的值，指针移动并且数据交换后的结果如下：
然后再开始从前往后遍历，直到low=high结束循环，此时low或者high的下标就是基准数据23在该数组中的正确索引位置，如下图所示：
这样一遍遍的走下来，可以很清楚的知道，快排的本质就是把比基准数据小的都放到基准数的左边，比基准数大的数都放到基准数的右边，这样就找到了该数据在数组中的正确位置。
然后采用递归的方式分别对前半部分和后半部分排序，最终结果就是自然有序的了。
代码实现
public class QuickSort {
public static void main(String[] args) {
int[] array = {2,4,1,5,67,2,45,78,3,9};
quickSort(array,0,array.length-1);
System.out.println(Arrays.toString(array));
}
public static void quickSort(int[] array,int low,int high){
if(low < high){
//找到基准数据位置
int index = getIndex(array,low,high);
//递归
quickSort(array,0,index-1);
quickSort(array,index+1,high);
}
}
//获取基准数据位置
public static int getIndex(int[] array,int low,int high){
//一般取第一个数作为基准数据
int tmp = array[low];
while(low < high){
while(low < high && array[high] >= tmp){
high--;
}
//否则high处元素小于基准数据，将high处赋值给low处数据
array[low] = array[high];
//赋值完后，需要从前面开始扫描数组
while(low < high && array[low] <= tmp){
low++;
}
array[high] = array[low];
}
//整个循环结束时high=low,但是该位置处不等于基准元素
array[low] = tmp;
return low;
}
}
输出结果：
[1, 2, 2, 3, 4, 5, 9, 45, 67, 78]
特点分析
最好情况下快排每次能恰好均分序列，那么时间复杂度就是O(nlogn)，最坏情况下，快排每次划分都只能将序列分为一个元素和其它元素两部分，这时候的快排退化成冒泡排序，时间复杂度为O(n^2)。
- 平均时间复杂度是O(nlogn)
- 最坏时间复杂度是O(n^2)
- 对于大的，乱序排列的数组来说快排一般是已知的最快的已知排序
- 快排是一种不稳定排序
插入排序
原理
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
思路
将一个数据插入到已经排好序的有序数据中
- 将要排序的是一个乱的数组
int[] arrays = {3, 2, 1, 3, 3}; - 在未知道数组元素的情况下，我们只能把数组的第一个元素作为已经排好序的有序数据，也就是说，把
{3}看成是已经排好序的有序数据
第一趟排序：
用数组的第二个数与第一个数(看成是已有序的数据)比较
- 如果比第一个数大，那就不管他
- 如果比第一个数小，将第一个数往后退一步，将第二个数插入第一个数去
第二趟排序：
用数组的第三个数与已是有序的数据{2,3}(刚才在第一趟排的)比较
- 如果比2大，那就不管它
- 如果比2小，那就将2退一个位置，让第三个数和1比较
在第二步中：
- 如果第三个数比1大，那么将第三个数插入到2的位置上
- 如果第三个数比1小，那么将1后退一步，将第三个数插入到1的位置上
...
后面依此类推
代码实现
public class InsertSort {
public static void main(String[] args) {
int[] array = {2,4,1,5,67,2,45,78,3,9};
insertSort(array);
}
public static void insertSort(int[] arr) {
if (arr.length < 2)
System.out.println(Arrays.toString(arr));
for (int i = 1;i < arr.length;i++) {
for (int j = i;j > 0;j--) {
if (arr[j-1] > arr[j]) {
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
} else {
break;//插入新的元素
}
}
}
System.out.println(Arrays.toString(arr));
}
}
输出结果：
[1, 2, 2, 3, 4, 5, 9, 45, 67, 78]
特点分析
- 最坏时间复杂度为O(n^2)
- 最好时间复杂度为O(n)
- 平均时间复杂度为O(n^2)
- 插入排序是一种稳定的排序算法。
选择排序
原理
选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
思路
举例：数组 int[] arr={5,2,8,4,9,1}
第一趟排序： 原始数据：5 2 8 4 9 1
最小数据1，把1放在首位，也就是1和5互换位置，
排序结果：1 2 8 4 9 5
第二趟排序：
第1以外的数据{2 8 4 9 5}进行比较，2最小，
排序结果：1 2 8 4 9 5
第三趟排序：
除1、2以外的数据{8 4 9 5}进行比较，4最小，8和4交换
排序结果：1 2 4 8 9 5
第四趟排序 :
除第1、2、4以外的其他数据{8 9 5}进行比较，5最小，8和5交换
排序结果：1 2 4 5 9 8
第五趟排序：
除第1、2、4、5以外的其他数据{9 8}进行比较，8最小，8和9交换
排序结果：1 2 4 5 8 9
代码实现
public class SelectionSort {
public static void main(String[] args) {
int[] array = {2,4,1,5,67,2,45,78,3,9};
selectionSort(array,0,array.length-1);
System.out.println(Arrays.toString(array));
}
public static void selectionSort(int[] array,int start,int end){
for(int i = 0; i < array.length ;i++){
int k = i;
for(int j = k + 1; j < array.length; j++){
if(array[j] < array[k]){
k = j; //记下目前找到的最小值所在的位置
}
}
//在内层循环结束，也就是找到本轮循环的最小的数以后，再进行交换
if(i != k){ //交换a[i]和a[k]
int temp = array[i];
array[i] = array[k];
array[k] = temp;
}
}
}
}
输出结果：
[1, 2, 2, 3, 4, 5, 9, 45, 67, 78]
特点分析：
- 最坏时间复杂度为O(n^2)
- 平均时间复杂度为O(n^2)
- 选择排序是一种不稳定的排序
归并排序
原理
归并排序（merge sort）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
思路
比如我们对[8,4,5,7,1,3,6,2]这个数组进行归并排序，我们首先利用分治思想的“分”将数组拆分。
可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为
log2n。再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将
[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。
代码实现
public class MergeSort {
public static void main(String []args){
int[] array = {2,4,1,5,67,2,45,78,3,9};
sort(array);
System.out.println(Arrays.toString(array));
}
public static void sort(int []arr){
int []temp = new int[arr.length];//在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间
sort(arr,0,arr.length-1,temp);
}
private static void sort(int[] arr,int left,int right,int []temp){
if(left<right){
int mid = (left+right)/2;
sort(arr,left,mid,temp);//左边归并排序，使得左子序列有序
sort(arr,mid+1,right,temp);//右边归并排序，使得右子序列有序
merge(arr,left,mid,right,temp);//将两个有序子数组合并操作
}
}
private static void merge(int[] arr,int left,int mid,int right,int[] temp){
int i = left;//左序列指针
int j = mid+1;//右序列指针
int t = 0;//临时数组指针
while (i<=mid && j<=right){
if(arr[i]<=arr[j]){
temp[t++] = arr[i++];
}else {
temp[t++] = arr[j++];
}
}
while(i<=mid){//将左边剩余元素填充进temp中
temp[t++] = arr[i++];
}
while(j<=right){//将右序列剩余元素填充进temp中
temp[t++] = arr[j++];
}
t = 0;
//将temp中的元素全部拷贝到原数组中
while(left <= right){
arr[left++] = temp[t++];
}
}
}
输出结果：
[1, 2, 2, 3, 4, 5, 9, 45, 67, 78]
特点分析
- 归并排序是一种稳定排序
- Java中的
Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本 - 每次合并操作的时间复杂度为O(n)，完全二叉树的深度为
|log2n|，总的平均时间复杂度为O(nlogn) - 归并排序的最好、最坏、平均时间复杂度都为O(nlongn)
