| 算法 |
时间复杂度 |
原地排序 |
稳定排序 |
基于比较 |
| 冒泡 |
O(n^2) |
是 |
是 |
是 |
| 插入 |
O(n^2) |
是 |
是 |
是 |
| 选择 |
O(n^2) |
是 |
不 |
是 |
| 快排 |
O(nlongn) |
是 |
不 |
是 |
| 归并 |
O(nlongn) |
不 |
是 |
是 |
| 堆排 |
O(nlongn) |
是 |
不 |
是 |
| 桶排序 |
O(n) |
不 |
是 |
不 |
| 基数排序 |
O(dn)d是维度 |
不 |
是 |
不 |
要点：最大的数像一个泡泡冒出水面的样子落到数组最后的位置，而这个冒出的动作是通过逐个交换做到的，i记录泡泡落在的位置。
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int e = arr.length - 1; e > 0; e--) {
for (int i = 0; i < e; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
}
}
}
}
public static void swap(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}要点：维护一个有序数列，i为右边界（有序数列不包括i），每次将i位置的数插入有序数列中，当i到达最后的时候就代表数组有序，插入操作通过逐个交换完成。
public static void insertionSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 1; i < arr.length; i++) {
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
}
public static void swap(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}要点：遍历未排序区间（i--arr.length-1）选择最小的元素并予以key标记，然后将该最小元素与首元素i进行交换，随着i后移来完成排序。非稳定排序。
public static void selectionSort(int[] arr) {
if (arr == null || arr.length < 2)
return;
for (int i = 0; i < arr.length - 1; i++) {
int key = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[key]) {
key = j;
}
}
swap(arr, i, key);
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}要点：将数组中某一个数作为标杆（随机），小于该数的放在数组的前一部分，大于该数的放在数组后一部分，等于该数的放在中间部分。对前后两部分继续该操作以完成整个排序。
public static void quickSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int l, int r) {
if (l < r) {
swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
int[] p = partition(arr, l, r);
quickSort(arr, l, p[0]);
quickSort(arr, p[1], r);
}
}
public static int[] partition(int[] arr, int l, int r) {
int less = l - 1;
int more = r;
while (l < more) {
if (arr[l] < arr[r]) {
swap(arr, ++less, l++);
} else if (arr[l] > arr[r]) {
swap(arr, --more, l);
} else {
l++;
}
}
swap(arr, more, r);
return new int[] { less, more + 1};
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}要点：归并排序采用二分的思想，将排序整个数组转换成三部分，a.把左半部分排序，b.将右半部分排序，c.将两部分合并。而左右部分各自的排序也是按照这三步递归的进行下去。
public static void mergeSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
mergeSort(arr, 0, arr.length - 1);
}
public static void mergeSort(int[] arr, int l, int r) {
if (l == r) {
return;
}
int mid = l + ((r - l) >> 1);
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
public static void merge(int[] arr, int l, int m, int r) {
int[] help = new int[r - l + 1];
int i = 0;
int p1 = l;
int p2 = m + 1;
while (p1 <= m && p2 <= r) {
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
while (p1 <= m) {
help[i++] = arr[p1++];
}
while (p2 <= r) {
help[i++] = arr[p2++];
}
for (i = 0; i < help.length; i++) {
arr[l + i] = help[i];
}
}解析：求数组中逆序对的数目，借助归并排序的思想，将数组折半并将求解子数组的逆序对，然后计算两个数组之间的逆序对，将三个逆序对个数相加。
public int InversePairs(int [] array) {
if (array == null || array.length < 1)return 0;
return run(array, array.clone(), 0, array.length - 1)%1000000007;
}
public int run(int[] arr, int[] copy, int start, int end){
if (start == end){
copy[start] = arr[start];
return 0;
}
int mid = start + ((end - start) >> 1);
//子数组的逆序对
int left = run(copy, arr, start, mid) % 1000000007;
int right = run(copy, arr, mid + 1, end) % 1000000007;
int i = mid;
int j = end;
int count = 0;
int index = end;
while (i >= start && j>= mid + 1){
if (arr[i] > arr[j]){
copy[index--] = arr[i--];
count += j - mid;
if(count>=1000000007)//数值过大求余
{
count%=1000000007;0
}
}else{
copy[index--] = arr[j--];
}
}
for (;i >= start; i--){
copy[index--] = arr[i];
}
for (;j >= mid + 1; j--){
copy[index--] = arr[j];
}
return (left + right + count)%1000000007;
}解析：给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
public ListNode mergeKLists(ListNode[] lists) {
if (lists.length == 0)return null;
sort(lists, 0, lists.length - 1);
return lists[0];
}
public void sort(ListNode[] lists, int start, int right){
if (start < right){
int mid = start + ((right - start) >> 1);
sort(lists, start, mid);
sort(lists, mid + 1, right);
lists[start] = merge(lists[start], lists[mid + 1]);
}
}
public ListNode merge(ListNode l1, ListNode l2){
ListNode head = new ListNode(0);
ListNode tmp = head;
while (l1 != null && l2 != null){
if (l1.val <= l2.val){
tmp.next = l1;
l1 = l1.next;
}else{
tmp.next = l2;
l2 = l2.next;
}
tmp = tmp.next;
}
if (l1 != null){
tmp.next = l1;
}
if (l2 != null){
tmp.next = l2;
}
return head.next;
}要点：首先就是将初始的数据构建成一个大根堆，然后将堆顶的元素与数组最后一个元素进行交换，重新将堆调整成大根堆，重复交换调整的过程直到堆的size归零。
public static void heapSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
int size = arr.length;
swap(arr, 0, --size);
while (size > 0) {
heapify(arr, 0, size);
swap(arr, 0, --size);
}
}
public static void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
public static void heapify(int[] arr, int index, int size) {
int left = index * 2 + 1;
while (left < size) {
int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;
largest = arr[largest] > arr[index] ? largest : index;
if (largest == index) {
break;
}
swap(arr, largest, index);
index = largest;
left = index * 2 + 1;
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}要点：根据数据的分布情况构建桶，根据数据的值将数据放入到桶对应的位置，然后依次倒出元素完成排序。
public static void bucketSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
}
int[] bucket = new int[max + 1];
for (int i = 0; i < arr.length; i++) {
bucket[arr[i]]++;
}
int i = 0;
for (int j = 0; j < bucket.length; j++) {
while (bucket[j]-- > 0) {
arr[i++] = j;
}
}
}