java 排序

java排序的简单介绍
1.直接排序
就是在原有的有序数组里面将数插进合适位置，从而使数组有序，但这种排序方式时间复杂度高，为O（ n^2）,但为稳定排序

点击查看代码

public void insertSort(int[] array){int i ;for (i = 1; i < array.length; i++) {int j ;int tmp = array[i];for (j =  i - 1; j >= 0; j--) {if(tmp < array[j]){array[j + 1] = array[j];}else {break;}}array[j + 1] = tmp;}}

2.希尔排序，将数组分组后进行排序，分组内成员为数组内相同距离的数，随着组的减少到1时，就可以将数组排序，相当于直接插入排序的优化，是不稳定排序

点击查看代码

public void shellSort(int[] array){int gap = array.length;while (gap > 1){gap /= 2;shell(array,gap);}}private void shell(int[] array, int gap) {for (int i = gap; i < array.length; i++) {int tmp = array[i];int j = i - gap;for (j = i - gap; j >= 0; j -= gap) {if(tmp < array[j]){array[j + gap] = array[j];}else {break;}}array[j + gap] = tmp;}}

3. 堆排序 用堆来进行排序，递增排序用大根堆，递减用小根堆根据堆得特质可知根节点用于是最大或最小值，只需将值根节点移到最后一位然后让数量减1就可以实现排序

点击查看代码

public void heapSort(int[] array){createHeap(array);int end = array.length - 1;while (end > 0){swap(array,0,end);siftDown(array,0,end);end--;}}private void createHeap(int[] array) {for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {siftDown(array,parent,array.length);}}private void siftDown(int[] array,int parent, int length){int child = parent * 2 + 1;while (child < length){if(child + 1 < length && array[child + 1 ] > array[child]){child++;}if (array[parent] < array[child]){swap(array,parent,child);parent = child;child = parent * 2 + 1;}else {break;}}}

4.直接选择排序 选择出里面最大或最小或二者的数，然后放在第一或最后一位，时间复杂度高

点击查看代码

public void selectSort(int[] array){for (int i = 0; i < array.length; i++) {int minIndex = i;for (int j = i + 1; j < array.length; j++) {if(array[j] < array[minIndex]){minIndex = j;}}swap(array,i,minIndex);}}private void swap(int[] array, int i, int minIndex) {int index = array[i];array[i] = array[minIndex];array[minIndex] = index;}public void selectSort2(int[] array){int left = 0;int right = array.length - 1;while (left < right){int minIndex = left;int maxIndex = left;for (int i = left + 1; i <= right ; i++) {if(array[minIndex] > array[i]){minIndex = i;}if(array[maxIndex] < array[i]){maxIndex = i;}}swap(array,minIndex,left);if(left == maxIndex){maxIndex = minIndex;}swap(array,maxIndex,right);right--;left++;}}

5.冒泡排序 通过遍历数组将每一位放在合适的位置来进行排序，可以定义个boolean类型，如果没有在进行交换就直接跳出循环

点击查看代码

public void bubbleSort(int[] array){for (int i = 0; i < array.length - 1; i++) {boolean flg = false;for (int j = 0; j < array.length - 1 - i; j++) {if(array[j] > array[j + 1]){swap(array,j,j + 1);}flg = true;}if(flg == false){break;}}}

6.快速排序 类似于二叉树的思想，选定一个值，将比这个值大的放在右边，小的放在左边，重复该过程，知道所有元素放在对应的位置 而这共有三种方法，hoare，挖坑和前后指针法，最重要的是挖坑法，这里就实现hoare和挖坑

点击查看代码

public void quickSort(int[] array){quick1(array,0,array.length - 1);}private void quick(int[] array,int start,int end){if(start >= end){return;}int pivot = partition(array,start,end);quick(array,start,pivot - 1);quick(array,pivot + 1,end);}//挖坑法public int partition(int[] array,int left,int right){int i = left;int tmp = array[left];while (left < right){while (left < right && array[right] >= tmp){right--;}array[left] = array[right];while (left < right && array[left] <= tmp){left++;}array[right] = array[left];}array[left] = tmp;return left;}private int partitionHoare(int[] array,int left,int right){int i = left;int tmp = array[left];while (left < right){while (left < right && array[right] >= tmp){right--;}while (left < right && array[left] <= tmp){left++;}swap(array,left,right);}swap(array,i,left);return left;}

快速排序的优化 三数取中法，在正常情况下，有可能选定的值是最大或最小值，导致效率变低，所以我们就选择个中位数来作为基准值 在递归到小范围时，可以用直接插入排序来提升效率

点击查看代码

private void quick1(int[] array,int start,int end){if(start >= end){return;}if(end - start <= 15){insertSort(array,start,end);return;}int index = getmiddleNum(array,start,end);swap(array,index,start);int pivot = partition(array,start,end);quick(array,start,pivot - 1);quick(array,pivot + 1,end);}private void insertSort(int[] array,int left,int right){int i = left + 1;for(;i < right;i++){int tmp = array[i];int j = i - 1;for (; j >= 0 ; j--) {if(tmp < array[j]){array[j + 1] = array[j];}else {break;}}array[j + 1] = tmp;}}/*求中位数下标*/private int getmiddleNum(int[] array,int left,int right){int mid = (left+ right) / 2;if(array[left] > array[right]){if (array[right] > array[mid]) {return right;}else if(array[mid] > array[left]){return left;}else {return mid;}}else {if(array[left] > array[mid]){return left;}else if(array[mid] > array[right]){return right;}else {return mid;}}}

7.归并排序 和快速排序有点类似，将待排序的数分组，使每一组都有序，然后合并成更大的有序数组，直到全部合成就有序了

点击查看代码

public void mergeSort(int[] array){mergeSortFun(array,0,array.length - 1);}private void mergeSortFun(int[] array, int start, int end) {if(start >= end){return;}int mid = (start + end) / 2;mergeSortFun(array,start,mid);mergeSortFun(array,mid + 1, end);merge(array,start,mid,end);}private void merge(int[] array, int start, int mid, int end) {int[] tmp = new int[end - start + 1];int s1 = start;int e1= mid;int s2 = mid + 1;int e2 = end;int k = 0;while (e1 >= s1 && e2 >= s2){if (array[s1] > array[s2]) {tmp[k] = array[s2];k++;s2++;}else {tmp[k] = array[s1];k++;s1++;}}while (e1 >= s1){tmp[k] = array[s1];k++;s1++;}while (e2 >= s2){tmp[k] = array[s2];k++;s2++;}for (int i = 0; i < tmp.length; i++) {array[i + start] = tmp[i];}}