一、快速排序
基本思想：快速排序是对冒泡排序的一种改进，通过一趟排序将要排序的数据分割成独立的两部分，其中一部分是所有数据都要比另外一部分的所有数据都要小，然后再按此方法对这两部分数据进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
图解如下图所示：
代码如下：
public class QuickSort {
public static void main(String[] args) {
int[] arr = new int[]{12,34,24,15,6,8,65};
sort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr,int left,int right){
while (left > right){
return;
}
int i = left;
int j = right;
int base = arr[left];
while (i!=j) {
while (i < j && arr[j] >= base) {
j--;
}
while (i < j && arr[i] <= base) {
i++;
}
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
arr[left] = arr[i];
arr[i] = base;
sort(arr,0,i-1);
sort(arr,j+1,right);
}
}
结果如下所示：
二、归并排序
基本思想：①归并排序，首先把一个数组中的元素，按照某一方法，先拆分了之后，按照一定的顺序 各自排列，然后再归并到一起，使得归并后依然是有一定顺序的 。
②归并排序算法可以利用递归的思想或者迭代的思想去实现。首先我 们先把一个无序的数组去拆分，然后利用一定的规则，去合并。类似于二叉树的结构。其总的时间复杂度为O( n log n)。空间复杂度为 S（n）因为最大的空间使用量为该排序数组的最大个数。
图解如下：
代码如下：
public class MergeSortDemo {
public static void main(String[] args) {
int[] arr = {2,5,7,6,4,9,1,3,8};
int[] temp = new int[arr.length];
mergeSort(arr,0,arr.length-1,temp);
System.out.println(Arrays.toString(arr));
}
//分
public static void mergeSort(int[] arr,int left,int right,int[] temp){
if (left < right){
int mid = (left + right)/2;
mergeSort(arr,left,mid,temp);
mergeSort(arr,mid +1,right,temp);
merge(arr,left,mid,right,temp);
}
}
//合并
public 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[t++] = arr[i++];
}
while (j <= right){
temp[t++] = arr[j++];
}
t = 0;
int tempLeft = left;
while (tempLeft <= right){
arr[tempLeft++] = temp[t++];
}
}
}
结果如下：
三、基数排序（空间换时间 稳定）
基本思想：将所有比较的数值统一为一样的数值长度，数位较短的数前面补零，然后从最低位开始，依次进行一次排序，这样从最低位排序依次到最高位排序以后，数列就变成一个有序序列。
图解如下：
代码如下：
public class RadixSort {
public static void main(String[] args) {
int[] arr = {53,3,542,748,214,65,941,14};
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void radixSort(int[] arr){
int max = arr[0];
for (int i=1;i
结果如下：
四、堆排序
基本介绍：
①堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序的、是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定的；
②堆是具有一定性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值称为大顶堆。
③每个结点的值都小于或等于其左右孩子结点的值称为小顶堆。
堆排序的基本思想：
①将待排序序列构造成一个大顶堆
②此时，整个序列的最大值就是堆顶的根结点。
③将其与末尾元素进行交换，此时末尾就为最大值。
④然后将剩余n-1个元素重新构成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了。
代码如下：
public static void main(String[] args) {
int[] arr = {5,9,3,7,6,8,2,14};
heapSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void heapSort(int[] arr){
int temp = 0;
//从第一个非叶子结点开始遍历比较
for (int i=arr.length / 2 - 1;i>=0;i--){
adjustHeap(arr,i,arr.length);
}
for (int j=arr.length - 1;j>0;j--){
temp = arr[0];
arr[0] = arr[j];
arr[j] = temp;
adjustHeap(arr,0,j);
}
}
public static void adjustHeap(int[] arr,int i,int length){
int temp = arr[i];
for (int k = 2 * i + 1;k < length;k = 2 * k + 1){
if (k + 1 < length && arr[k] < arr[k + 1]){
k++;
}
if (arr[k] > temp){
arr[i] = arr[k];
i = k;
}else{
break;
}
}
arr[i] = temp;
}
}
结果如下：
