排序算法汇总

一、二分查找

public static int binarySearch(int[] nums,int target){int l = 0, r = nums.length-1;while(l <= r){int mid = l + (r-l)/2;if(nums[mid] == target){return mid;}else if(nums[mid] < target){r = mid - 1;}else{l = mid + 1;}}return -1;}

对于防止溢出的 mid = l + (r - l ) /2;操作，也可以使用 mid = (l + r)>>>2; 但这里无符号右移等价除法仅适用于操作数是正数的情况。

对于二分查找的填空类笔试题，遵循：

- 奇数二分取中间

- 偶数二分取中间靠左

的原则。

二、排序

（一）冒泡排序

每次判断比较相邻两个位置的数字，直到末尾，在末尾确定一个数组中最大/最小的元素，这是一轮冒泡。

每一轮冒泡都确定好一个元素的位置，所以一共要进行nums.length - 1轮

 public static void bubble(int[] nums){for(int j = 0 ; j < nums.length ;j++){for(int i = 0 ; i < nums.length - 1 ; i++){if(nums[i] > nums[i+1]){swap(nums,i,i+1);}}}}public static void swap(int[] nums, int i , int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}

优化：

（1）每一轮冒泡不必都是nums.length - 1 次，每进行一轮，都可以少比较一次，因为结尾多确定了一位元素。

要减去的次数恰好是外层循环进行的次数，因此 i < nums.length - 1 - j 即可

 public static void bubble(int[] nums){for(int j = 0 ; j < nums.length ;j++){for(int i = 0 ; i < nums.length - 1 - j ; i++){if(nums[i] > nums[i+1]){swap(nums,i,i+1);}}}}public static void swap(int[] nums, int i , int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}

（2）当数组有序时，没有必要再进行冒泡了。

即当一次冒泡没有交换之后，就结束冒泡。

在每一轮冒泡前，增添一个标志位为false，swap时置为true，如果没有交换过，那么直接break.

public static void bubble(int[] nums){for(int j = 0 ; j < nums.length - 1;j++){boolean swapped = false;for(int i = 0 ; i < nums.length - 1 - j; i++){if(nums[i] > nums[i+1]){swap(nums,i,i+1);swapped = true;}}if(!swapped){break;}}}public static void swap(int[] nums, int i , int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}

（3）每一轮冒泡要比较的次数仍然可以改进，实际上，只需要记录下上一轮冒泡最后交换元素的下标是多少，在这之后没有发生过交换，说明这之后的元素是有序的，这个下标即为本轮冒泡要比较的次数。

这种优化方法融合了（1）和（2），并考虑了更多

最终实现：

public static void bubble2(int[] nums){int n  = nums.length - 1;for(;;){int last = 0;for(int i = 0 ; i < n ; i++){if(nums[i] > nums[i+1]){swap(nums,i,i+1);last = i;}}n = last;if(n == 0){break;}}}public static void swap(int[] nums, int i , int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}

关于上面这个实现如何理解：

（1）last就是记录的上一次交换的位置，这也是下一次冒泡要比较的次数

（2）last是最外层for循环内的局部变量，每次进来都是0，为了利用到last，添加的n，记录上一次的last；同时，last为0时（由n判断）也可以及时break，起到优化（2）的效果

（3）优化完以后，会发现最外层冒泡几轮已经完全由last（n）、i控制，最外层for循环的j不再需要，因此最外层的循环条件可以删除。

冒泡排序文字描述：

1.依次比较数组中相邻两个元素的大小，若a[i]>a[i+1],则交换两个元素，两两比较完一次称为一轮冒泡，一轮冒泡的结果是让最大的元素排到了最后

2.重复以上步骤，直到整个数组有序。

3.优化方式：每一轮冒泡时，最后一次交换的索引可以作为下一轮冒泡的比较次数，如果这个值为0，表示整个数组有序，直接退出外层循环即可。

（二）选择排序

选择排序每一轮从未排序部分选择一个最小的，放在已排序部分的最后，进行nums.length - 1轮后使数组有序。

最外层的遍历轮数也即本轮从未排序部分找出最小的元素要交换到的索引位置。

public static void selection(int[] nums){for(int i = 0; i < nums.length - 1 ; i++){int s = i;for(int j = i + 1 ; j < nums.length ; j++){if(nums[j] < nums[s]){s = j;}}if(s != i){swap(nums,s,i);}}}public static void swap(int[] nums, int i , int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}

选择排序描述：

1.将数组分为两个子集，排序的和未排序的，每一轮从未排序的子集中选出最小的元素，放到排序子集的后面。

2.重复以上步骤，直到整个数组有序。

优化方式：

为了减少交换次数，每一轮先找到最小的索引，最后进行交换，这样可以让每一轮只进行一次交换。

与冒泡排序比较：

（1）二者的平均时间复杂度都是O(n^2)

（2）选择排序一般快于冒泡，因其交换次数少

（3）当集合有序度高时，冒泡优于选择

（4）冒泡排序是稳定算法，选择排序是不稳定算法

（三）插入排序

插入排序也将集合视为有序部分和无序部分，但插入排序是顺序扩大有序部分的。

与冒泡一样，对于有序数组排序的时间复杂度是O(n)

public static void insert(int[] nums){//i代表待插入元素的索引for(int i = 1 ; i < nums.length ; i++){//t 代表待插入元素的值int t = nums[i];//j 代表有序区的索引int j = i - 1;while(j >= 0){if(nums[j] > t){nums[j+1] = nums[j];j--;}else{break;}}nums[j+1] = t;}}

插入排序描述：

（1）插入排序将数组分为有序区和无序区，每一轮将无需区的第一个元素插入到有序区中，扩大有序区。与选择排序不同的是，插入排序扩大有序区需要保证顺序（即通过每次都是插入无序区的第一个元素来保证）

（2）重复以上步骤，直到整个数组有序

优化方式：

（1）待插入元素进行比较时，需要比自己小的元素，就代表找到了插入位置，可以跳出循环，不必进行后续的比较了。

（2）插入时可以直接移动元素，而不是交换元素。（交换的话需要中间变量，执行的语句更多，这是与冒泡的swap相比的）

插入排序与选择排序比较：

（1）二者平均时间复杂度都是O(n^2)

（2）大部分情况下，插入都略优于选择

（3）有序集合插入的时间复杂度为O(n)

（4）插入排序属于稳定排序算法，选择排序属于不稳定排序算法。

（四）希尔排序

插入排序存在一个缺点：如果一个较大元素一开始排在前半部分的话，这个较大元素需要移动较多次数才能够移动到数组的后半部分。

希尔排序将间隙相同的元素划为一组。同一组的元素进行插入排序。间隙不断减小，减小到1时完成排序。通过这样的方式在实际上增加了大元素的移动步数，从而解决了大元素每次移动一步，需要很多步才能移动到数组后半部分的问题。

（五）快速排序

1.单边循环快排（lomuto洛穆托分区方案）

（1）选择最右元素为pivot

（2）j指针负责找到比pivot小的元素，i指针指向待交换的元素，一旦j指针找到则与i进行交换

（3）i指针维护小于基准点元素的边界，也是每次交换的目标索引

（4）最后基准点与i交换，i即为分区位置。

public class Sort {public static void main(String[] args) {int[] nums= {3,2,3,1,2,4,5,5,6};quickSort(nums,0,nums.length-1);for (int num : nums) {System.out.println(num);}}public static void quickSort(int[] nums,int l , int h){if(l >= h) return ;int p = partition(nums,l,h);quickSort(nums,l,p-1);quickSort(nums,p+1,h);}//partition负责一次划分//return 基准点元素所在的正确索引public static int partition(int[] nums,int l , int h){int pivot = nums[h];int i = l ;for(int j = l ; j < h; j++){if(nums[j] < pivot){swap(nums,i,j);i++;}}swap(nums,i,h);return i;}public static void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}}

2.双边循环快排

（1）选择最左元素作为基准点元素

（2）j指针负责从右向左找比基准点小的元素，i指针负责从左向右找比基准点大的元素，一旦找到二者相交，直至i，j相交

（3）最后基准点与i（此时i与j相等）交换，i即为分区位置

在代码里有以下要注意的细节：

a.外层循环条件有i<j,内层也要有i<j.避免单次移动时过界

b.必须先找j，再找i，否则会在最后一次swap时出现问题，会把比pivot大的值交换到前面去

c.寻找i时while循环条件是<=，因为要跳过pivot自身

public static void main(String[] args) {int[] nums= {3,2,3,1,2,4,5,5,6};quickSort(nums,0,nums.length-1);for (int num : nums) {System.out.println(num);}}public static void quickSort(int[] nums,int l , int h){if(l >= h) return ;int p = partition2(nums,l,h);quickSort(nums,l,p-1);quickSort(nums,p+1,h);}public static int partition2(int[] nums,int l , int h){int i = l, j = h;int pivot = nums[i];while(i < j){while(i < j && nums[j] > pivot) j--;while(i < j && nums[i] <= pivot) i++;swap(nums,i,j);}swap(nums,l,j); //此时i和j重合return j;//此时i和j重合}public static void swap(int[] nums, int i, int j) {int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}

快速排序的特点：

1.平均时间复杂度O(nlogn),但如果数组元素都是重复元素，快速排序的性能会受影响，最坏时间复杂度O(n^2)

2.数据量较大时，优势非常明显

3.属于不稳定排序

应用：leetcode 215.TopK问题

class Solution {public int findKthLargest(int[] nums, int k) {k = nums.length - k + 1;return quickSort3(nums,0,nums.length-1,k);}public static int quickSort3(int[] nums,int l , int h , int k){if(l >= h) return nums[l];int p = partition2(nums,l,h);//下标为p处，前面有p个元素if(p == k-1) return nums[p];else if(p > k-1) return quickSort3(nums,l,p-1,k);else return quickSort3(nums,p+1,h,k);}public static int partition2(int[] nums,int l , int h){int i = l, j = h;int pivot = nums[i];while(i < j){while(i < j && nums[j] > pivot) j--;while(i < j && nums[i] <= pivot) i++;swap(nums,i,j);}swap(nums,l,j); //此时i和j重合return j;//此时i和j重合}public static void swap(int[] nums,int i , int j){int tmp = nums[i];nums[i] = nums[j];nums[j] = tmp;}
}