基础复习 —— 排序
性能总览
性质
稳定性
按比较的标准，两元素相等时，不会改变这两个元素的相对顺序。
意义是，在按某一标准进行排序时，不打乱按其他标准已经排好的顺序。
例：（A, 2), (B, 1), (C, 3), (D, 2) 本身已经按字母排序，若对数字排序，非稳定的排序可能会将D放到A前面，而稳定的排序可以确保A, D间顺序不变。
就地性
是否需要额外的空间存放辅助数组，还是直接在要排序的数组上操作就可以。
另外，无关就地性，如果希望输入的数组不要被改动，可以在排序前先复制数组再操作。
// 例，利用Arrays.copyOf
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);自适应性
时间复杂度受元素分布影响。
能找到的相关资料不多，可能这个说法不太常见，但用处应该是，在已经近似是有序（知道无序元素并不多）的条件下，有自适应性的排序算法拥有更低的时间复杂度。
比较类
基于元素之间的比较（>, <, =）来进行排序。
速度
一般情况下：快速>归并>希尔>堆
数据规模 快速排序 归并排序 希尔排序 堆排序
1000万 0.75 1.22 1.77 3.57
5000万 3.78 6.29 9.48 26.54
1亿 7.65 13.06 18.79 61.31冒泡排序
{无序，有序}，每次比较无序部分中相邻的两个元素，顺序错误就交换过来。每轮循环可以确保一个最大/最小被找到并放在最边缘（成为整个序列后方有序序列的一部分）。
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length-1 ; i++) {
boolean flag = true; // 跳出旗帜
// 如果一轮内循环中没有进行过交换
// 说明前方的顺序已经全部是正确的，可以停止继续排序了
for (int j = 0; j < arr.length - i; j++) {
// i每加1，后面就多一位已经排好的，不许要进入下轮内循环
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = false; // 标记有过交换
}
}
if (flag) { // 没有交换，已经排好了
break;
}
}
}
选择排序
每次循环都找到最大/最小元素的位置，然后交换到开头/结尾。
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
// i 为第(i+1)小元素应该在的位置
// arr.length - 1 因为后面只剩一个元素的时候就不用交换了。。。
int min = i; // 用于记录最小元素位置，之后交换到位置i
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
if (i != min) {
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
}插入排序
类似整理扑克牌，把整个数组看做 {有序序列，无序序列} （一开始只把第一个元素看做有序，后面全是无序）。从无序序列里拿东西建造前面的有序序列，直到无序序列消耗完。
每次把无序序列中第一个元素插进有序序列它该在的地方（有序序列长度+1，无序序列长度-1）。
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
// 第0个跳过，直接看做只有1个元素的有序序列
// 无序从第1个开始
int tmp = arr[i];
int j = i;
while (j > 0 && tmp < arr[j - 1]) {
// 拿着tmp那个无序，把比它大的有序往右移腾地方
arr[j] = arr[j - 1];
j--;
}
if (j != i) {
arr[j] = tmp; // 把tmp插过去
}
}
}希尔排序
每次以一定的步长把整个序列划分成若干子序列，分别对这些子序列进行插入排序，并逐渐减小步长，直至最后步长为1。
[3, 5, 9, 2, 4, 1, 6, 7, 8, 10]
例，步长为5时，子序列分别为：
[3, 1], [5,6], [9,7], [2,8], [4,10]，分别排序后 --> [1,3], [5,6], [7,9], [2,8], [4,10]
此轮排序后--> [1,5,7,2,4,3,6,9,8,10]
（如每次步长缩短至原来的一半后向下取整）缩短步长至2，此时子序列为：
[1,7,4,6,8], [5,2,3,9,10]， 分别排序后 --> [1,4,6,7,8], [2,3,5,9,10]
此轮排序后 --> [1,2,4,3,6,5,7,9,8,10]
最后经一轮步长为1的插入排序
public static void shellSort(int[] arr) {
int length = arr.length;
int temp;
for (int step = length / 2; step >= 1; step /= 2) {
for (int i = step; i < length; i++) {
temp = arr[i];
int j = i - step;
while (j >= 0 && arr[j] > temp) {
arr[j + step] = arr[j];
j -= step;
}
arr[j + step] = temp;
}
}
}- 希尔排序中比较糟糕的情况：临近几轮step互为倍数的情况，会导致上一轮已经排好序的数字们又被归在同一组进行排序，降低效率
快速排序
使用分治法（Divide and conquer）的一种排序，速度通常较快。每次选择一个值为基准（一般直接取序列第一个值），把比它小的全挪动到它左边。然后，以这个值为分界，对它左边、右边的序列分别进行快速排序（递归），直到每个要排序的序列长度都为1，就排好了。
public class QuickSort {
public static void main(String[] args) {
// 实验
int[] arr = {3,1,8,2,4,5,2,-1,0,9,10,-2,-5,4,6};
sort(arr);
}
public static int[] sort(int[]arr){
quickSort(arr,0,arr.length-1);
return arr;
}
private static void quickSort(int[] arr, int left, int right) {
if(left<right){// 则包含left,right的序列长度>=2
int partition_index = partition(arr, left, right);
quickSort(arr,left, partition_index-1);
quickSort(arr,partition_index+1, right);
}// 即，当每个子序列只剩1个元素，结束排序
}
private static int partition(int[] arr, int left, int right) {
//int left_ = left, right_ = right; // 只是为了打印，不要在意
int base = arr[left]; // 基准值
while(left<right){
while(left<right && arr[right]>=base){
// 从右向左找小于base的元素
// 大于base的不管，直接跳过
// 如果一路都没有小于base的，内外循环就都结束了。。。
right--;
}
arr[left] = arr[right]; //换到最左边（base的位置）
while(left<right && arr[left]<=base){
// 从左往右找大于base的元素
left++;
}
arr[right] = arr[left]; // 放到刚才刚才那个小于base元素的位置
}
arr[left] = base; // 出循环，left,right指向同一个位置
// 左边没有比base大的,右边没有比base小的
/*
System.out.println("---partition----base:"+base+"(pos:"+left+")");
System.out.println("---range: pos"+left_+"(val in outcome:"+arr[left_]+
") ~ pos"+right_+"(val in outcome:"+arr[right_]+")");
System.out.println("---outcome---"+Arrays.toString(arr));
System.out.println(); // 打印结果（快速排序的中间过程）
*/
return left; // 返回base/partition的位置
}
}- 每次执行QuickSort其实是把基准值放在它正确的位置（左边所有数比它小，右边所有数比它大，那么它一定已经在正确位置上）
归并排序
- 把整个无序序列里的元素拆成一个一个的
- 拿两个单个元素组成有序序列
- 拿两个由两个单个元素组成有序序列组成有序序列
- 拿两个由两个有序序列组成的有序序列组成有序序列
- 拿两个由两个由两个有序序列组成的有序序列组成的有序序列组成有序序列
- ……
你懂的:)
(其实大概拿3、4、5个也无所谓，只是两个写着比较方便……)
public class MergeSort {
public static void main(String[] args) {
// 测试
int[] arr = {3,1,8,2,4,5,2,-1,0,9,10,-2,-5,4,6,-11,0,0,0,3,4};
int[] res = sort(arr);
System.out.println("---final result: "+Arrays.toString(res));
}
public static int[] sort(int[]arr){
int[] res = mergeSort(arr);
return res;
}
private static int[] mergeSort(int[] arr) {
if(arr.length>=2){ //折半
int mid = arr.length/2; // 拆分拆分，直到每个列表只剩一个元素
int[] left = mergeSort(Arrays.copyOfRange(arr, 0, mid));
int[] right = mergeSort(Arrays.copyOfRange(arr, mid, arr.length));
return merge(left,right); // 然后把两个有序序列重组
}
return arr; //会一直递归到每个序列只剩1个元素
}
private static int[] merge(int[] l1, int[] l2){
// l1、l2都是有序序列
int i=0, j=0,c=0;
int len1 = l1.length;
int len2 = l2.length;
int len3 = len1+len2;
int[] res = new int[len3];
while(i<len1 && j<len2){ // 两个序列都还有元素时
// 插小的那个元素，然后移动指针到下一位
// 也有不记录指针位置，看做两个队列，每次poll序列开头的
if(l1[i]<=l2[j]){
res[c++] = l1[i++];
}
else {
res[c++] = l2[j++];
}
}
// 有一个序列空了
// 把另一个序列里剩下的直接全塞进result
while(i<len1){
res[c++] = l1[i++];
}
while(j<len2){
res[c++] = l2[j++];
}
/*
// 打印本轮合并的结果
System.out.println("---merge");
System.out.println("---l1: "+Arrays.toString(l1));
System.out.println("---l2: "+Arrays.toString(l2));
System.out.println("---outcome: "+Arrays.toString(res));
System.out.println();*/
return res; // res依然是个有序序列
}
}堆排序
一种使用最大/最小堆来记录部分比较的过程，从而加速的选择排序。不使用额外空间的原地排序，但不稳定。也可以用来寻找最大/最小的N个值（top N问题）。
看上去的样子是：
{最大（或最小）堆：记录了部分比较过程的无序序列，有序序列}
堆
拿数组存储的完全二叉树。Ni 的父节点为N(i-1)/2 ，左子节点为N2i+1 ，右子节点为N2i+2 。
最大堆：每个节点大于等于其子节点
最小堆：每个节点小于等于其子节点
步骤
- 构建一个最大（最小）堆，即寻找无序区中的最大（最小）值
- 把堆顶（堆里的最大/最小值）与最后一个元素交换。此时，len缩短1，把最后一个元素从堆的范围移除（把最大/最小值划入有序序列部分）。
- 维护堆/无序区，使它重新成为最大（最小）堆（即从无序区找出最大/最小值。
- 重复第二、三步，直至所有元素从无序区（堆）划分至有序区。
public class HeapSort {
public static void main(String[] args) {
int[] arr = {3,1,8,2,4,5,2,-1,0,9,10,-2,-5,4,6,-11,0,0,0,3,4};
sort(arr);
System.out.println("---final result: "+Arrays.toString(arr));
}
public static void sort(int[]arr){
int len = arr.length;
// 构建最大堆
// 从倒数第二层（非叶子），依次与子节点比较并把较大的交换上去
for (int i = (len-2) / 2; i >= 0; i--) {
heapify(arr, i, len);
}
for (int i = len - 1; i > 0; i--) {
swap(arr, 0, i); // 取堆顶的最大值，与最后的节点交换
len--; // 把这轮的最大值划分出去
heapify(arr, 0, len); // 堆的部分重新排序
}
}
private static void heapify(int[] arr, int i, int len) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;
if (left < len && arr[left] > arr[largest]) {
// 若左子节点存在，且比父节点大
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
// 右子节点存在，且比父节点大
largest = right;
}
if (largest != i) {
swap(arr, i, largest); // 把较大的节点换上去
heapify(arr, largest, len); //largest现在是原来的i
// 看交是否需要把它继续往下置换
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}基数排序
按位排序，用于排序整数或可以用整数表示的数据（如日期、字符）。
例：[12, 25, 11, 15, 46, 42, 23, 35, 40,13]
按个位排序
0: 40----1: 11----2:12, 42----3: 23, 13---- 5: 25, 15, 35-—6:46
[40, 11, 12, 42, 23, 13, 25, 15, 35, 46]
按十位排序
1: 11, 12, 13, 15----2: 23, 25-—3:35-—4:40, 42, 46
[11, 12, 13, 15, 23, 25, 35, 40, 42, 46]
//LSD Radix Sort
var counter = [];
function radixSort(arr, maxDigit) {
var mod = 10;
var dev = 1;
for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
for(var j = 0; j < arr.length; j++) {
var bucket = parseInt((arr[j] % mod) / dev);
if(counter[bucket]==null) {
counter[bucket] = [];
}
counter[bucket].push(arr[j]);
}
var pos = 0;
for(var j = 0; j < counter.length; j++) {
var value = null;
if(counter[j]!=null) {
while ((value = counter[j].shift()) != null) {
arr[pos++] = value;
}
}
}
}
return arr;
}桶排序
像是搞HashMap一样先搞一堆桶，然后按某种函数映射把元素塞进各个桶（但其实基本就是把整个区间分成n段，然后把属于该段的元素放进该段），每个桶分别排序，最后再把每个桶里排好序的倒出来拼在一起。。。
function bucketSort(arr, bucketSize) {
if (arr.length === 0) {
return arr;
}
var i;
var minValue = arr[0];
var maxValue = arr[0];
for (i = 1; i < arr.length; i++) {
if (arr[i] < minValue) {
minValue = arr[i];
} else if (arr[i] > maxValue) {
maxValue = arr[i];
}
}
//桶的初始化
var DEFAULT_BUCKET_SIZE = 5; // 设置桶的默认容量为5
bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
var buckets = new Array(bucketCount);
for (i = 0; i < buckets.length; i++) {
buckets[i] = [];
}
//利用映射函数将数据分配到各个桶中
for (i = 0; i < arr.length; i++) {
buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
}
arr.length = 0;
for (i = 0; i < buckets.length; i++) {
insertionSort(buckets[i]); // 对每个桶进行排序，这里使用了插入排序
for (var j = 0; j < buckets[i].length; j++) {
arr.push(buckets[i][j]);
}
}
return arr;
}