文章目录
一， 直接插入排序二，希尔排序三、选择排序四，堆排序五，冒泡排序六，快速排序如何优化快排呢？三数取中法优化快排
七，归并排序
怎么判断是不是稳定的排序呢？ 如果当前这个序列，在排序的过程中，没有发生跳跃式的交换，那么我们就认为这个排序是稳定的排序。
一， 直接插入排序
特点：效率低，容易实现。 原理：将数组分为两部分，将后部分元素逐一插入前部分有序元素的适当位置 时间复杂度：最好 当数据有序时O(n) 最坏 O(n^2) 空间复杂度 O（1） 稳定的排序
public static void insertSort(int[] array){
for(int i=1;i int tmp=array[i];//后部分第一个数 int j=i-1; for(;j>=0;j--){ if(array[j]>tmp){ array[j+1]=array[j]; }else { break; } } array[j+1]=tmp; } } 二，希尔排序 原理：希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。 先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。 时间复杂度：最好O(n) 最坏O(n^2) 空间复杂度 O（1） 不稳定的排序 保证gap是素数，最后一个是1就可以了 public static void shell(int[] array ,int gap) { for(int i=gap;i int tmp=array[i]; int j=i-gap; for(;j>=0;j=j-gap){ if(array[j]>tmp){ array[j+gap]=array[j]; }else{ break; } } array[j+gap]=tmp; } } public static void shellSort(int[] array){ int[] drr={5,3,1};//增量数组 for(int i=0;i shell(array,drr[i]); } } 三、选择排序 时间复杂度：O(n^2) 空间复杂度 O（1） 不稳定的排序 特点：效率低，容易实现。 原理：就是每次遍历一趟，找出最小的数，放到最前端，直到全部待排序的数据元素排完。 （这里说的是最前，是指无序的队列中的最前） public static void selectSort(int[] array) { for (int i = 0; i < array.length-1; i++) { for (int j = i+1; j < array.length; j++) { if(array[j] < array[i]) { int tmp = array[j]; array[j] = array[i]; array[i] = tmp; } } } } 四，堆排序 原理：是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。 时间复杂度：O(logn) 空间复杂度 O（1） 不稳定的排序 public class Priority { //从小到大排序 public static void heapSort(int[] array){ crateBigHeap(array); int end=array.length-1; while(end>0){ int tmp=array[0]; array[0]=array[end]; array[end]=tmp; adjustDown(array,0,end); end--; } } public static void adjustDown(int[] array,int parent, int len) { int child = 2 * parent + 1; //child while (child < len) { // child + 1 < len 判断是 当前是否 有右孩子 if (child + 1 < len && array[child] < array[child + 1]) { child++;// } // child 下标 一定是 左右孩子的最大值下标 if (array[child] > array[parent]) { int tmp = array[child]; array[child] = array[parent]; array[parent] = tmp; parent = child; child = 2 * parent + 1; } else { //因为是从最后一棵树开始调整的 只要我们 找到了这个 // this.elem[child] <= this.elem[parent] 后续就不需要循环了 //后面的都已经是大根堆了 break; } } } public static void crateBigHeap(int[] array) { for (int i = (array.length - 1 - 1) / 2; i >= 0; i--) { adjustDown(array,i, array.length); } } 五，冒泡排序 最常见的排序实现起来很简单，不过实际应用很少，复杂度O(n²)。 原理：如果假设长度为n的数组array,按照从小到大排序，首先从数组的第一个元素开始到数组最后一个元素为止，对数组中相邻的两个元素进行比较，如果位于数组左端的元素大于数组右端的元素，则交换这两个元素在数组中的位置，此时数组最右端的元素即为该数组中所有元素的最大值。接着对该数组剩下的n-1个元素进行冒泡排序，直到整个数组有序排列。算法的时间复杂度为O(n^2)。 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 针对所有的元素重复以上的步骤，除了最后一个。 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 时间复杂度：O(n^2) 空间复杂度 O（1） 稳定的排序 public static void BubbleSort(int []array){ for(int i=1;i for(int j=0;j if(array[j]>array[j+1]) { int temp=array[j]; array[j]=array[j+1]; array[j+1]=temp; } } for(int i=0;i System.out.print(array[i]+" "); } System.out.println(); } } 六，快速排序 特点：高效，时间复杂度最好为O(nlogn)最坏O（n^2）。 空间复杂度：O（logn) 不稳定的排序 原理：1. 从待排序区间选择一个数，作为基准值(pivot) 2. 遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可以包含相等的）放到基准值的右边； 3. 采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 == 1，代表已经有序，或者小区间的长度 == 0，代表没有数据。 分治思想什么时候效率最高？每次把待排序序列均匀的划分为若干份 //快速排序 public static int pivot(int[] array,int start,int end) { int tmp = array[start]; while (start < end) { while (start end--; } //把数据赋值给start array[start]=array[end]; while (start start++; } //把start下标的值给end array[end]=array[start]; } array[start] = tmp; return start; } public static void quick(int [] array,int low,int high){ if(low int piv= pivot(array,low,high); quick(array,low,piv-1); quick(array,piv+1,high); } } public static void main(String[] args) { int[] array={12,32,1,3,4,5,45,6,88,77}; System.out.println(Arrays.toString(array)); quick(array,0,array.length-1); System.out.println(Arrays.toString(array)); } } 如何优化快排呢？ 随机选取基准法 做法：随机找到后边的一个下标，然后和Low下标的数据进行交换，然后以low下标交换的值作为基准 三数取中法优化快排 //快速排序 public static int pivot(int[] array,int start,int end) { int tmp = array[start]; while (start < end) { while (start end--; } //把数据赋值给start array[start]=array[end]; while (start start++; } //把start下标的值给end array[end]=array[start]; } array[start] = tmp; return start; } public static void swap(int[] array,int k,int i){ int tmp=array[k]; array[k]=array[i]; array[i]=tmp; } //快速排序的优化 public static void medianOfThree(int [] array,int low,int high){ int mid=(low+high)/2; //array[mid]<=array[low]<=array[high] if(array[low] //array[mid] <= array[low] swap(array,mid,low); } if(array[low]>array[high]){ //array[low] <= array[high] swap(array,high,low); } if(array[mid] //array[mid] <= array[high] swap(array,mid,high); } } public static void quick(int [] array,int low,int high){ if(low medianOfThree(array,low,high); int piv= pivot(array,low,high); quick(array,low,piv-1); quick(array,piv+1,high); } } public static void main(String[] args) { int[] array={12,32,1,3,4,5,45,6,88,77}; System.out.println(Arrays.toString(array)); quick(array,0,array.length-1); System.out.println(Arrays.toString(array)); } } 七，归并排序 原理：采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列;即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。归并排序是一种稳定的排序方法。 //合并 public static void merge(int[] array,int start,int mid,int end) { int s1 = start; int s2 = mid+1; int[] tmp = new int[end-start+1]; int k = 0;//tmp数组的下标 while (s1 <= mid && s2 <= end) { if(array[s1] <= array[s2]) { tmp[k++] = array[s1++]; }else{ tmp[k++] = array[s2++]; } } //有可能第一个段还有数据 有可能第2个段也有数据 while (s1 <= mid) { tmp[k++] = array[s1++]; } while (s2 <= end){ tmp[k++] = array[s2++]; } for (int i = 0; i < tmp.length; i++) { array[i+start] = tmp[i]; } } //分解 public static void mergeSortInternal(int[] array,int low,int high) { if(low >= high) return; int mid = (low+high)/2; mergeSortInternal(array,low,mid); mergeSortInternal(array,mid+1,high); //合并的操作 merge(array,low,mid,high); } public static void mergeSort(int[] array){ mergeSortinternal(array,0,array.length-1); } public static void main(String[] args) { int[] array={12,32,1,3,4,5,45,6,88,77}; System.out.println(Arrays.toString(array)); mergeSort(array); System.out.println(Arrays.toString(array)); }