JAVA-数据结构-排序

1.直接插入排序

1.原理：和玩扑克牌一样，从左边第二个牌开始，选中这个，和前面的所有牌比较，插在合适的位置

public static void insertsort(int[] arr){//直接插入排序for (int i = 1; i < arr.length; i++) {//此循环用来从1开始确定牌的位置int j = i-1;//得到j前面一个元素int tmp = arr[i];//将i处元素取出来，用来作比较for (; j >=0 ; j--) {//此循环用来和i前面的比较，将i放在正确的位置if(arr[j] > tmp){arr[j+1] = arr[j];//若i前面的比i大则将前面的值赋值给后面}else{
//                    arr[j+1] = tmp;break;//比前面都要大，没有比较的必要}}arr[j+1] = tmp;//j走完上面循环为-1，上面走完一次循环j=0时为空，}}

直接插入排序特点

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

2.希尔排序

希尔排序是直接插入排序的Promax版本，将直接插入排序分为n份，比较完n份，排序即成功

思想：先选定一个整数，把待排序文件中所有记录分成多个组，
所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达
=1时，所有记录在统一组内排好序。

public static void shellSort(int[] array){//希尔排序是直接插入排序的优化int gap = array.length;while(gap > 0){//将每组距离最终干为1，即可成功gap /= 2;//得到每组的距离shell(array,gap);}}public static void shell(int[] array,int gap){for (int i = gap; i < array.length; i++) {int tmp = array[i];int j = i - gap;for (; j >= 0; j--) {if(array[j] > tmp){array[j+gap] = array[j];}else{array[j+gap] = tmp;break;}}array[j+gap] = tmp;}}

3.选择排序

基本思想：一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元
素排完 。

 public static void selsctSort1(int[] array){//选择排序基础版for (int i = 0; i < array.length; i++) {int minIndex = i;//每循环一次确定一个从左往右的最小值int j = i+1;for (; j <array.length; j++) {if(array[minIndex] > array[j]){minIndex = j;//将minTndex和j的下标先进行交换,找到最小的和其交换}//从一次次循环中得出在[i,length）的最小值}swap(array,minIndex,i);}}public static void selsctSort(int[] array){//选择排序promax版int left = 0;int right = array.length-1;while (left < right){int minIndex = left;int maxIndex = left;//统一从没排序的起点开始for (int i = left+1; i < array.length; i++) {if(array[maxIndex] < array[i]){maxIndex = i;}if(array[minIndex] > array[i]){minIndex = i;}}swap(array,left,minIndex);swap(array,right,maxIndex);left++;right--;}}public static void swap(int[]array ,int minIndex,int j){int tmp = array[j];array[j] = array[minIndex];array[minIndex] = tmp;}
}

总结：
1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

4. 堆排序

 降序建大堆，升序建小堆

详情思路请看之前写的堆部分

https://mp.csdn.net/mp_blog/creation/editor/139502440

 /*** 堆排序* 时间复杂度：O(n*logN)* 空间复杂度：O(1)* 稳定性：不稳定* @param array*/public static void heapSort(int[] array) {createHeap(array);int end = array.length-1;while (end > 0) {swap(array,0,end);siftDown(array,0,end);end--;}}private static void createHeap(int[] array) {for (int parent = (array.length-1-1)/2; parent >= 0; parent--) {siftDown(array,parent,array.length);}}/**** @param array* @param parent 每棵子树调整的根节点* @param length 每棵子树调整的结束节点*/private static void siftDown(int[] array, int parent, int length) {int child = 2 * parent + 1;while (child < length) {if(child + 1 < length && array[child] < array[child+1]) {child++;}if(array[child] > array[parent]) {swap(array, parent, child);parent = child;child = 2*parent+1;}else {break;}}}

6.快速排序

思想：任取待排序元素序列中的某元
素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有
元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

翻译过来实现过程就是取第一个数，分别在头和尾定义一个指针 ，头指针找比第一个数大的（需求就是把小的放在左边所以需要找大的和右边大的交换），尾指针找比第一个小的，两个都找到后，进行交换，确保左边的都是小于或等于第一个数的，右边都是大于或等于第一个数的，直到两个指针位置相等，然后再交换第一个与它们的位置，通过递归将它们分为一个个更小的然后即可完成

快速排序Hoare法实现过程

问题：为什么先从后面开始

如果先从前面开始则会造成最后汇合点大于key.

递归法

通过left和right的不断变化，直到left与right相遇为止，当不断分为很多的left和right后，

public class Sort {public static void swap(int[]array ,int minIndex,int j){int tmp = array[j];array[j] = array[minIndex];array[minIndex] = tmp;}public static void qsort(int[] array){int left = 0,right = array.length-1;parttrtions(array,left,right);}private static void parttrtions(int[]array,int left,int right){if(left>=right){return;}int start = parttrtion(array,left,right);parttrtions(array,left,start-1);parttrtions(array,start+1,right);}private static int parttrtion(int[] array,int left,int right){//Hoare版int privt = array[left];int end = right,start = left;while(start<end){while(start<end&& array[end] >= privt) {//从右往左直到找到比array[start](privt)小的放在end--;}while(start<end&&array[start] <= privt){//跳出小循环说明找到了比privt大的数start++;}swap(array,left,start);}return start;}private static int parttrtion1(int[] array,int left,int right){//挖坑法int privt = array[left];int end = right,start = left;while(start<end){while(start<end&& array[end] >= privt) {//从右往左直到找到比array[start](privt)小的放在end--;}array[start] = array[end];//将end下标的值来补充start的空缺while(start<end&&array[start] <= privt){//跳出小循环说明找到了比privt大的数start++;}array[end] = privt;//将start下标的值来补充end的空缺}return start;}
}

 快排的优化：

1.三数取中法：如果是单一的数则可能造成，单支树的产生，最高造成N(O*2),所以可以提前将中间的值给到start,这样能极大减少计算量

private static int getMiddleNum(int[] array,int left,int right) {int mid = (left+right)/2;if(array[left] < array[right]) {if(array[mid] < array[left]) {return left;}else if(array[mid] > array[right]) {return right;}else {return mid;}}else {if(array[mid] > array[left]) {return left;}else if(array[mid] < array[right]) {return right;}else {return mid;}}}

非递归法

 利用栈后进先出不断变化left和right的值

public static void qsort1(int[] array){int left = 0,right = array.length-1;int par = parttrtion(array,left,right);Stack<Integer> stack = new Stack<>();if(par>left+1){stack.push(left);stack.push(par-1);}if(par < right-1){stack.push(par+1);stack.push(right);}while(!stack.empty()){right = stack.pop();left = stack.pop();par = parttrtion(array,left,right);if(par>left+1){stack.push(left);stack.push(par-1);}if(par < right-1){stack.push(par+1);stack.push(right);}}}

总结： 

 1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：O(N*logN)

3. 空间复杂度：O(logN)
4. 稳定性：不稳定

7.归并排序

思想：先将数组分成很多小份，然后再进行排序，然后把排序完的数组重新整和，最终得到一个有序数组。

递归法

1.首先将大数组分为小数组，把大问题拆分为小问题，1.找到最底层的两个数组，2.排序

 public void mergeSortTmp(int[]a,int left,int right){//将数组先分开再合并if(left>=right){return;}int mid = (left+right)/2;mergeSortTmp(a,left,mid);//分成很多份，找到最左边mergeSortTmp(a,mid+1,right);//上层递归完成，找到对应要排序的另一个数组merge(a,mid,left,right);//两个都找到后，进行排序操作}

2.然后利用两个数组组合排序的方法，定义两个指针，取到小的添加到新的数组

private void merge(int[]a,int mid,int left,int right){int [] array = new int[right-left+1];int set = 0;int s1 = left;int e1 = mid;int s2 = mid+1;int e2 = right;while(s1<e1&&s2<e2){if(a[s1] < a[s2]){array[set++] = a[s1++];}else {array[set++] = a[s2++];}}while (s1 <= mid) {array[set++] = array[s1++];}while (s2 <= right) {array[set++] = array[s2++];}for (int i = 0; i < array.length; i++) {a[i+left] = array[i];//分组后每一小组的下标并不是零}}

非递归法

思路：我们这个排序的核心就是1.一步步得到最小数组 2.一步步将两个小数组合并起来直到得到 大数组

所以可以在循环里嵌套循环，外面决定数组长度，里面循环将小数组排序合并，外循环设置每个小数组的相隔距离

 public void mergrSort1(int[] array){int left = 0,right = array.length-1;int gap = 1;//gap负责将数组分为array.length/2while(gap<array.length){for (int i = 0; i < array.length; i+=2*gap) {//得到小一号的数组并且进行排序合并,里面for循环是为了得到最多组数组left = i;int mid = left+gap-1;right = mid+gap;if(mid >= array.length) mid=array.length-1;if(right>=array.length) right = array.length-1;merge(array,mid,left,right);}gap *= 2;//世界线收束，每次小数组排序好后，再将更大数组排序}}}

总结：1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定

8.计数排序

思路：将原数组遍历一遍，得到原数组的最大值和最小值，将最大值和最小值相减，得到它们的取值范围，创建一个新数组，然后将对应的值给到，和其相对相等的下标，（比如数组的值为1给到开辟数组的1下标，）然后遍历新数组，赋值给原数组

/*** 计数排序：* 时间复杂度：O(范围 + n )*       范围越大  越慢* 空间复杂度：O(范围)* 稳定性：* @param array*/public static void countSort(int[] array) {//1. 找最大值 和 最小值 来确定 计数数组的大小int maxVal = array[0];int minVal = array[0];for (int i = 1; i < array.length; i++) {if(array[i] < minVal) {minVal = array[i];}if(array[i] > maxVal) {maxVal = array[i];}}int len = maxVal - minVal + 1;int[] count = new int[len];//2. 遍历原来的数组array把 每个元素 放到对应的计数数组当中 进行计数for (int i = 0; i < array.length; i++) {int index = array[i];count[index-minVal]++;}//3.依次 遍历计数数组 O(范围)int index = 0;for (int i = 0; i < count.length; i++) {while (count[i] != 0) {array[index] = i+minVal;index++;count[i]--;}}}

总结 

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。
2. 时间复杂度：O(MAX(N,范围))
3. 空间复杂度：O(范围)
4. 稳定性：稳定