Java-＞排序_IT分享知识网

 public static void insertSort(int[] array) { for (int i = 1; i < array.length; i++) { int j = i - 1; int tmp = array[i]; for (; j >= 0; j--) { if(array[j] > tmp) { //if(arr[j] >= tmp) //变为不稳定的排序 array[j+1] = array[j]; }else { // array[j+1] = tmp; break; } } array[j+1] = tmp; } }

如果一个排序本身就是稳定的排序那么它就可以被实现为不稳定的排序，

但是一个排序本身就是不稳定的排序那么它不可能被实现为稳定的排序

1.2希尔排序(缩小增量法)

先选定一个整数，把待排序文件分为整数个组，再进行每个组内的排序

跳跃式分组:

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

1.3直接插入排序和希尔排序的耗时比较

import java.util.Arrays; import java.util.Random; public class Text { public static void readyDataOrder(int[] array) { Random random = new Random(); for (int i = 0; i < array.length; i++) { array[i] = random.nextInt(); } } public static void InsertOrder(int[] array) { array = Arrays.copyOf(array,array.length); long start = System.currentTimeMillis(); Sort.insertSort(array); long end = System.currentTimeMillis(); System.out.println("插入排序耗时参考：" + (end - start)); } public static void ShellOrder(int[] array) { long start = System.currentTimeMillis(); Sort.shellSort(array); long end = System.currentTimeMillis(); System.out.println("希尔排序耗时参考：" + (end - start)); } public static void main(String[] args) { int[] array = new int[]; readyDataOrder(array); InsertOrder(array); ShellOrder(array); } } //插入排序耗时参考：1884 //希尔排序耗时参考：22

2.选择排序

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

2.1直接选择排序

 public static 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 static void swap(int[] array, int i, int minIndex) { int tmp = array[i]; array[i] = array[minIndex]; array[minIndex] = tmp; }

 private static void swap(int[] array, int i, int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } public static void select2Sort(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[i] < array[minIndex]) { minIndex = i; } if(array[i] > array[maxIndex]) { maxIndex = i; } } swap(array,left,minIndex); //第一个数据是最大值 if(maxIndex == left) { maxIndex = minIndex; } swap(array,right,maxIndex); left++; right--; } } //复杂度不变

2.2堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆

 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 swap(int[] array, int i, int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } public static void createHeap(int[] array) { for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) { siftDown(array,parent,array.length); } } private static void siftDown(int[] array,int parent,int len) { int child = parent * 2 + 1; while(child < len) { if(child + 1 < len && array[child] < array[child + 1]) { child++; } if(array[child] > array[parent]) { swap(array,child,parent); parent = child; child = parent * 2 + 1; }else { break; } } }

2.3直接选择排序与堆排序的耗时比较

public class Text { public static void main(String[] args) { int[] array = new int[]; readyDataOrder(array); InsertOrder(array); ShellOrder(array); selectOrder(array); select2Order(array); heaptOrder(array); } public static void readyDataOrder(int[] array) { Random random = new Random(); for (int i = 0; i < array.length; i++) { array[i] = random.nextInt(); } } public static void InsertOrder(int[] array) { array = Arrays.copyOf(array,array.length); long start = System.currentTimeMillis(); Sort.insertSort(array); long end = System.currentTimeMillis(); System.out.println("插入排序耗时参考：" + (end - start)); } public static void ShellOrder(int[] array) { array = Arrays.copyOf(array,array.length); long start = System.currentTimeMillis(); Sort.shellSort(array); long end = System.currentTimeMillis(); System.out.println("希尔排序耗时参考：" + (end - start)); } public static void selectOrder(int[] array) { array = Arrays.copyOf(array,array.length); long start = System.currentTimeMillis(); Sort.selectSort(array); long end = System.currentTimeMillis(); System.out.println("选择排序耗时参考：" + (end - start)); } public static void select2Order(int[] array) { array = Arrays.copyOf(array,array.length); long start = System.currentTimeMillis(); Sort.select2Sort(array); long end = System.currentTimeMillis(); System.out.println("选择排序2耗时参考：" + (end - start)); } public static void heaptOrder(int[] array) { array = Arrays.copyOf(array,array.length); long start = System.currentTimeMillis(); Sort.heapSort(array); long end = System.currentTimeMillis(); System.out.println("堆排序耗时参考：" + (end - start)); } } //插入排序耗时参考：2098 //希尔排序耗时参考：25 //选择排序耗时参考：4093 //选择排序2耗时参考：2929 //堆排序耗时参考：16

3.交换排序

所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

3.1冒泡排序

 public static void bubbleSort(int[] array) { //i是趟数 for (int i = 0; i < array.length - 1; i++) { for (int j = 0; j < array.length - 1 - i; j++) { if(array[j] > array[j+1]) { swap(array,j,j+1); } } } } private static void swap(int[] array, int i, int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; }

优化：

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

3.2快速排序

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

1. Hoare版

 public static void quickSort(int[] array) { quick(array,0,array.length - 1); } private static void quick(int[] array, int left, int right) { if(left > right) return; int par = partition(array,left,right); quick(array,left,par-1); quick(array,par+1,right); } private static int partition(int[] array, int start, int end) { int i = start; int pivot = array[start]; while(start < end) { //先end后start while(start < end && array[end] >= pivot) { end--; } while(start < end && array[start] <= pivot) { start++; } swap(array,start,end); } swap(array,i,start); return start; } private static void swap(int[] array, int i, int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; }

//插入排序耗时参考：1983 //希尔排序耗时参考：19 //选择排序耗时参考：3844 //选择排序2耗时参考：2977 //堆排序耗时参考：14 //冒泡排序耗时参考：20525 //快速排序耗时参考：11

2. 挖坑法

 public static void quickSort(int[] array) { quick(array,0,array.length - 1); } private static void quick(int[] array, int left, int right) { if(left > right) return; int par = partition(array,left,right); quick(array,left,par-1); quick(array,par+1,right); } private static int partition(int[] array,int start,int end) { int pivot = array[start]; while(start < end) { while(start < end && array[end] >= pivot) { end--; } array[start] = array[end]; while(start < end && array[start] <= pivot) { start++; } array[end] = array[start]; } array[start] = pivot; return start; }

3. 前后指针

 public static void quickSort(int[] array) { quick(array,0,array.length - 1); } private static void quick(int[] array, int left, int right) { if(left > right) return; int par = partition(array,left,right); quick(array,left,par-1); quick(array,par+1,right); } private static int partition(int[] array,int start,int end) { int prev = start; int cur = start + 1; while(cur <= end) { if(array[cur] < array[start] && array[++prev] != array[cur]) { swap(array,cur,prev); } cur++; } swap(array,prev,start); return prev; } private static void swap(int[] array, int i, int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; }

3.2.1快速排序的优化

1.三数取中法选key

 private static void quick(int[] array, int left, int right) { if(left > right) return; int index = midThreeNum(array,left,right); swap(array,index,left); int par = partition(array,left,right); quick(array,left,par-1); quick(array,par+1,right); } //三数取中法选key public static int midThreeNum(int[] array, int start, int end) { int mid = (start + end) / 2; if(array[start] < array[end]) { if(array[mid] < array[start]){ return start; }else if(array[mid] > array[end]) { return end; }else { return mid; } }else { if(array[mid] > array[start]){ return start; }else if(array[mid] < array[end]) { return end; }else { return mid; } } }

2. 递归到小的子区间时，可以考虑使用插入排序

 public static void quickSort(int[] array) { quick(array,0,array.length - 1); } private static void quick(int[] array, int left, int right) { if(left > right) return; if(right - left + 1 == 7) { insertSort2(array,left,right); } int index = midThreeNum(array,left,right); swap(array,index,left); int par = partition(array,left,right); quick(array,left,par-1); quick(array,par+1,right); } //三数取中法选key public static int midThreeNum(int[] array, int start, int end) { int mid = (start + end) / 2; if(array[start] < array[end]) { if(array[mid] < array[start]){ return start; }else if(array[mid] > array[end]) { return end; }else { return mid; } }else { if(array[mid] > array[start]){ return start; }else if(array[mid] < array[end]) { return end; }else { return mid; } } } //递归到小的子区间时，可以考虑使用插入排序 private static void insertSort2(int[] array ,int start,int end) { for (int i = start + 1; i <= end; i++) { int j = i - 1; int tmp = array[i]; for (; j >= start; j--) { if (array[j] > tmp) { array[j + 1] = array[j]; } else { // array[j+1] = tmp; break; } } array[j + 1] = tmp; } } private static int partition(int[] array, int start, int end) { int i = start; int pivot = array[start]; while(start < end) { while(start < end && array[end] >= pivot) { end--; } while(start < end && array[start] <= pivot) { start++; } swap(array,start,end); } swap(array,i,start); return start; }

3.2.2非递归的快速排序

 public static void quickSort2(int[] array) { int left = 0; int right = array.length - 1; int par = partition(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.isEmpty()) { right = stack.pop(); left = stack.pop(); par = partition(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); } } } private static int partition(int[] array, int start, int end) { int i = start; int pivot = array[start]; while(start < end) { while(start < end && array[end] >= pivot) { end--; } while(start < end && array[start] <= pivot) { start++; } swap(array,start,end); } swap(array,i,start); return start; }

4.归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并

1.归并排序

 public static void mergeSort(int[] array) { mergeSortFunc(array,0,array.length - 1); } private static void mergeSortFunc(int[] array,int left,int right) { if(left == right) return; int mid =(left + right) / 2; //分解 mergeSortFunc(array,left,mid); mergeSortFunc(array,mid+1,right); //合并 merge(array,left,right,mid); } private static void merge(int[] array, int left, int right, int mid) { int s1 = left; int e1 = mid; int s2 = mid + 1; int e2 = right; int[] tmpArr = new int[right - left + 1]; int k = 0; while(s1<=e1 && s2<=e2) { if(array[s1] < array[s2]) { tmpArr[k++] = array[s1++]; }else { tmpArr[k++] = array[s2++]; } } while(s1<=e1) { tmpArr[k++] = array[s1++]; } while(s2<=e2) { tmpArr[k++] = array[s2++]; } for (int i = 0; i < tmpArr.length; i++) { array[i+left] = tmpArr[i]; } }

//插入排序耗时参考：2301 //希尔排序耗时参考：25 //选择排序耗时参考：4710 //选择排序2耗时参考：3635 //堆排序耗时参考：25 //冒泡排序耗时参考：23906 //快速排序耗时参考：40 //归并排序耗时参考：42

2.非递归的归并排序

 public static void mergeSort(int[] array) { int gap = 1; while (gap < array.length) { for (int i = 0; i < array.length; i += 2*gap) { int left = i; int mid = left + gap - 1; int right = mid + gap; if (mid >= array.length) { mid = array.length - 1; } if (right >= array.length) { right = array.length - 1; } merge(array, left, right, mid); } gap *= 2; } } private static void merge(int[] array, int left, int right, int mid) { int s1 = left; int e1 = mid; int s2 = mid + 1; int e2 = right; int[] tmpArr = new int[right - left + 1]; int k = 0; while (s1 <= e1 && s2 <= e2) { if (array[s1] < array[s2]) { tmpArr[k++] = array[s1++]; } else { tmpArr[k++] = array[s2++]; } } while (s1 <= e1) { tmpArr[k++] = array[s1++]; } while (s2 <= e2) { tmpArr[k++] = array[s2++]; } for (int i = 0; i < tmpArr.length; i++) { array[i + left] = tmpArr[i]; } }

3.海量数据的排序问题

5.排序算法复杂度及稳定性分析

排序方法	最好	平均	最坏	空间复杂度	稳定性
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定
插入排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定
希尔排序	O(n)	O(n^1.3)	O(n^2)	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^2)	O(log(n)) ~ O(n)	不稳定
归并排序	O(n * log(n))	O(n * log(n))	O(n * log(n))	O(n)	稳定

三、其他非基于比较排序

1.计数排序

计数排序的场景一定是数据集中在某各范围中

步骤：

 public static void countSort(int[] array) { //1.求 最大值 最小值 来确定 计数数组的大小 int min = array[0]; int max = array[0]; for (int i = 1; i < array.length; i++) { if(array[i] < min) { min = array[i]; } if(array[i] > max) { max = array[i]; } } int len = max - min + 1; int[] count = new int[len]; //2.遍历原来的数组 存放元素到计数数组中 //O(N) for (int i = 0; i < array.length; i++) { int index = array[i] - min; count[index]++; } //3.遍历计数数组 //O(范围) int arrIndex = 0; for (int i = 0; i < count.length; i++) { while(count[i]!=0) { array[arrIndex] = i + min; arrIndex++; count[i]--; } }

时间复杂度：O(范围 + N )

空间复杂度：O(范围)

稳定性：稳定

2.基数排序

动态图

队列，桶

3.桶排序

划分多个范围相同的区间，每个子区间自排序，最后合并

 public static void bucketSort(int[] array){ // 计算最大值与最小值 int max = array[0]; int min = array[0]; for(int i = 1; i < array.length; i++){ if(array[i] < min) { min = array[i]; } if(array[i] > max) { max = array[i]; } } // 计算桶的数量 int bucketNum = (max - min) / array.length + 1; ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum); for(int i = 0; i < bucketNum; i++){ bucketArr.add(new ArrayList<Integer>()); } // 将每个元素放入桶 for(int i = 0; i < array.length; i++){ int num = (array[i] - min) / (array.length); bucketArr.get(num).add(array[i]); } // 对每个桶进行排序 for(int i = 0; i < bucketArr.size(); i++){ Collections.sort(bucketArr.get(i)); } // 将桶中的元素赋值到原序列 int index = 0; for(int i = 0; i < bucketArr.size(); i++){ for(int j = 0; j < bucketArr.get(i).size(); j++){ array[index++] = bucketArr.get(i).get(j); } } }

4.比较

基数排序：根据键值的每位数字来分配桶；
计数排序：每个桶只存储单一键值；
桶排序：每个桶存储一定范围的数值;

5.排序

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/114546.html

Java-＞排序

一、排序

1.概念

2.常见的排序算法

二、常见排序算法的实现

1.插入排序

1.1直接插入排序