常见八大排序算法

今天我们带来数据结构中常见的8大排序算法。

排序算法	平均时间复杂度	最好情况	最坏情况	空间复杂度	稳定性
冒泡排序	O(n方)	O(n方)	O(n方)	O(1)	稳定
插入排序	O(n方)	O(n方)	O(n方)	O(1)	稳定
选择排序	O(n方)	O(n方)	O(n方)	O(1)	不稳定
希尔排序	O(n1.3方到1,5方)	O(n)	O(n方)	O(1)	不稳定
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	不稳定
快速排序	O(n log n)	O(n log n)	O(n方)	O(n log n)	不稳定
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	稳定
计数排序	O(n + k)	O(n + k)	O(n + k)	O(k)	不稳定

一，冒泡排序

思路：1，从头到尾比较相邻的元素，2，重复第一步n-1次

代码实现：

public void BubbleSort(int[] array){int[] str = Arrays.copyOf(array,array.length);for (int i = 0; i < str.length; i++) {for (int j = 0; j < str.length-1-i; j++) {if(str[j]<str[j+1]){swap(str,j,j+1);}}}System.out.println(Arrays.toString(str));}

swap是交换，

private void swap(int[] str,int i,int j){int tmp = str[i];str[i] = str[j];str[j] = tmp;}

代码优化： 优化也不会优化到多好基本还是O(n方的复杂度)

 public void BubbleSortLevel(int[] array){int[] str = Arrays.copyOf(array,array.length);for (int i = 0; i < str.length; i++) {boolean a = false;for (int j = 0; j < str.length-1-i; j++) {if(str[j]<str[j+1]){swap(str,j,j+1);a = true;}}if(!a){break;}}System.out.println(Arrays.toString(str));}

二，插入排序

思路； 1，定义两个下标i,j，tmp，i从1开始向后遍历，把初始的下标值赋给tmp 2，j每次从i前面开始向前遍历，比较j下标的元素和tmp的值。

代码实现：

public void InsertSort(int[] array){int[] str = Arrays.copyOf(array,array.length);int j=0;int tmp=0;for (int i = 1; i < str.length; i++) {tmp = str[i];for (j = i-1; j >=0 ; j--) {if(str[j]<tmp){str[j+1] = str[j];}else {break;}}str[j+1] = tmp;}System.out.println(Arrays.toString(str));}

三，选择排序

思路： 1，定义两个下标i，j；i从左向右遍历：2，我们创建一个tmpIndex记录i下标的值，j每次都在i的左边，与tmpIndex的值进行比较，记录新的tmpIndex的值，与i下标交换，重复这个步骤。

代码实现：

public void ChooseSort(int[] array){int[] str = Arrays.copyOf(array,array.length);int j= 0;int tmpIndex = 0;for (int i = 0; i < str.length; i++) {tmpIndex = i;for (j = i+1; j < str.length; j++) {if(str[j]<str[tmpIndex]){tmpIndex = j;}}swap(str,i,tmpIndex);}System.out.println(Arrays.toString(str));}

四，希尔排序

思路： 希尔排序实际就是多次进行快速排序，但是我们每次是不同的几组数进行排序，我们初始一个gap，gap的取值不一，我们一数组长度/2来赋给gap,每次相邻为gap的元素进行插入排序，再对gap/2，直到gap为1，我们的思路是插入排序对越有序的数组排序越有序

代码实现： 

    public void ShellSort(int[] array){int[] str = Arrays.copyOf(array,array.length);int gap = str.length/2;while (gap>=1){ShellSort__InsertSort(str,gap);gap/=2;}System.out.println(Arrays.toString(str));}private void ShellSort__InsertSort(int[] str,int gap){int tmp = 0;int j = 0;for (int i = gap; i < str.length; i++) {tmp = str[i];for (j = i-gap; j >= 0; j-=gap) {if(str[j]<tmp){str[j+gap] =str[j];}else {break;}}str[j+gap] = tmp;}}

五，堆排序

思路： 以升序为例，降序建小根堆，升序建大根堆，

1，建堆  2，栈顶元素与尾元素互换，再进行向下调整  3，直到重复步骤2直到0下标。

代码实现： 

public void HeapSort(int[] array){int[] str = Arrays.copyOf(array,array.length);CreateHeap(str);for (int i = str.length-1; i >=0 ; i--) {swap(str,i,0);ShiftDown(str,0,i);}System.out.println(Arrays.toString(str));}private void CreateHeap(int[] str){int c = str.length-1;int p = (c-1)/2;while (p>=0){ShiftDown(str,p,str.length);p--;}System.out.println(Arrays.toString(str));}private void ShiftDown(int[] str, int parent,int usdSize){int child = 2*parent+1;while (child<usdSize){if(child+1<usdSize && str[child]<str[child+1]){child++;}if(str[child]>str[parent]){swap(str,child,parent);parent = child;child = 2*parent+1;}else {break;}}}

六，快速排序

思路： 1，选择一个基准，定义两个下标，一个从右往左走（先走），一个从左往右走，右边遇到小于基准的与左边大于基准的交换，

2，找到基准，从基准左边和右边递归，重复1的过程。

代码实现（递归实现）：

public void QuickSort(int[] array){int[] str = Arrays.copyOf(array,array.length);QuickSortChild(str,0,str.length-1);System.out.println(Arrays.toString(str));}private void QuickSortChild(int[] str,int start,int end){if(start>end){return;}int left = start;int right = end;int part = partition(str,left,right);QuickSortChild(str,start,part-1);QuickSortChild(str,part+1,end);}private int partition(int[] str,int start,int end){int left = start;int right = end;int cmp = str[left];while (left<right){while (left<right && str[right]<=cmp){right--;}while (left<right && str[left]>=cmp){left++;}if(left<right){swap(str,left,right);}}swap(str,start,left);return left;}

代码优化（递归实现）：（三数取中法）

public void QuickSort2(int[] array){int[] str = Arrays.copyOf(array,array.length);QuickSortChild(str,0,str.length-1);System.out.println(Arrays.toString(str));}private void QuickSortChild2(int[] str,int start,int end){if(start>end){return;}int left = start;int right = end;int mid = middle(left,(left+right)/2,right);swap(str,start,mid);int part = partition(str,left,right);QuickSortChild(str,start,part-1);QuickSortChild(str,part+1,end);}private int partition2(int[] str,int start,int end){int left = start;int right = end;int cmp = str[left];while (left<right){while (left<right && str[right]<=cmp){right--;}while (left<right && str[left]>=cmp){left++;}if(left<right){swap(str,left,right);}}swap(str,start,left);return left;}private int middle(int left,int middle,int right){int[] arr = new int[]{left,middle,right};Arrays.sort(arr);return arr[1];}

 代码实现（非递归实现）：

public void QuickSort3(int[] array){int[] str = Arrays.copyOf(array,array.length);QuickSortChild3(str,0,array.length-1);System.out.println(Arrays.toString(str));}private void QuickSortChild3(int[] str,int start,int end){Deque<Integer> stack = new ArrayDeque<>();int part = partition3(str,start,end);if (part+1<end){stack.push(end);stack.push(part+1);}if(part-1>start){stack.push(part-1);stack.push(start);}while (!stack.isEmpty()){end = stack.pop();start = stack.pop();part = partition3(str,start,end);if (part+1<end){stack.push(end);stack.push(part+1);}if(part-1>start){stack.push(part-1);stack.push(start);}}}private int partition3(int[] str,int start,int end){int left = start;int right = end;int cmp = str[left];while (left<right){while (left<right && str[right]<=cmp){right--;}while (left<right && str[left]>=cmp){left++;}if(left<right){swap(str,left,right);}}swap(str,start,left);return left;}

七，归并排序

思路： 1，我们把数据平均分为两个部分定义左中右三个下标，左边递归，右边递归，

2，当左下标大于等于右递下标归停止，我们使用合并数组的方法，把每层递归后有序的左右子树有序化

代码实现：

public void MergeSort(int[] array){int[] str = Arrays.copyOf(array,array.length);MergeSortChild(str,0,str.length-1);System.out.println(Arrays.toString(str));}private void MergeSortChild(int[] str,int left, int right){if(left>=right){return;}int mid = (left+right)/2;MergeSortChild(str,left,mid);MergeSortChild(str,mid+1,right);MergeSort__new(str,left,mid,right);}private void MergeSort__new(int[] str,int left,int mid,int right){int s1 = left;int e1 = mid;int s2 = mid+1;int e2 = right;int[] arr = new int[right-left+1];int i=0;while (s1<=e1 && s2<=e2){if(str[s1]<=str[s2]){arr[i] = str[s1];i++;s1++;}if(str[s2]<str[s1]){arr[i] = str[s2];i++;s2++;}}while (s1<=e1){arr[i] = str[s1];i++;s1++;}while (s2<=e2){arr[i] = str[s2];i++;s2++;}for (int k = 0; k < i; k++) {str[k+left] = arr[k];}}

 

八，计数排序

计数排序适合排那些一定范围的大量数据，比如1-100的考试成绩

思路： 1，我们遍历原数组，找出最大值最小值，用他们的差值大小构建一个计数数组，

2，把原数组出现的数字-min放到计数数组里，有一个计数数组就加一，循环遍历计数数组，直到计数数组全部元素都为0

代码实现： 

public void CountIngSort(int[] array){int[] str = Arrays.copyOf(array,array.length);int max = str[0];int min = str[0];for (int i = 0; i <str.length ; i++) {if(str[i]>max){max = str[i];}if(str[i]<min){min = str[i];}}int[] count = new int[max-min+1];for (int i = 0; i < str.length; i++) {int a = str[i];count[a-min]+=1;}int j = 0;int i = 0;while (i<count.length) {while (count[i]!=0){str[j] = i+min;j++;count[i]--;}i++;}System.out.println(Arrays.toString(str));}