十大排序算法理解总结

🍀排序算法-平均时间复杂度排序算法

平均时间复杂度

稳定性

冒泡排序

O(n2)O(n^2)O(n2)

稳定排序

选择排序

O(n2)O(n^2)O(n2)

非稳定排序

插入排序

O(n2)O(n^2)O(n2)

稳定排序

希尔排序

O(n1.5)O(n^{1.5})O(n1.5)

非稳定排序

归并排序

O(n∗logN)O(n*logN)O(n∗logN)

稳定排序

堆排序

O(n∗logN)O(n*logN)O(n∗logN)

非稳定排序

快速排序

O(n∗logN)O(n*logN)O(n∗logN)

非稳定排序

计数排序

O(n+k)O(n+k)O(n+k)

稳定排序

基数排序

O(n+k))O(n+k))O(n+k))

稳定排序

桶排序

O(n+k)O(n+k)O(n+k)

稳定排序

🍀 O(n2)O(n^2)O(n2)的排序算法☘️冒泡排序两个数比较大小，如要求是升序排序，则较大的数往下沉，较小的数往上冒。

伪代码

代码语言：javascript代码运行次数：0运行复制BubbleSort(A)

for i = 1 to A.length-1

for j = A.length-1 downto i

if A[j] < A[j - 1]

exchange A[j] with A[j - 1]Java版

代码语言：javascript代码运行次数：0运行复制 public int[] BubbleSort(int[] list) {

int len = list.length;

for (int i = 1; i < len; i++) {

for (int j = len - 1; j >= i; j--) {

if(list[j] < list[j-1]) {

int tmp = list[j];

list[j] = list[j-1];

list[j-1] = tmp;

}

}

}

return list;

}Java泛型版

代码语言：javascript代码运行次数：0运行复制 public > T[] BubbleSort(T list[]) {

int len = list.length;

for (int i = 1; i < len; i++) {

for (int j = len - 1; j >= i; j--) {

if (list[j].compareTo(list[j - 1]) > 0) {

T tmp = list[j];

list[j] = list[j - 1];

list[j - 1] = tmp;

}

}

}

return list;

}1、时间复杂度：O(n2)O(n^2)O(n2)

2、空间复杂度：O(1)O(1)O(1)

3、稳定排序

4、原地排序

☘️选择排序每次选择最小或者最大的元素排列到有序区。 在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换； 第二次遍历n-2个数，找到最小的数值与第二个元素交换； 重复。。。 第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。

伪代码

代码语言：javascript代码运行次数：0运行复制SelectionSort(A)

for i=1 to A.length-1

min=i

for j=i+1 to A.length

if A[j]

min=j

tem=A[min]

A[min]=A[i]

A[i]=temJava版

代码语言：javascript代码运行次数：0运行复制 public int[] SelectionSort(int[] list) {

int len = list.length, minT;

for (int i = 0; i < len; i++) {

minT = i;

for (int j = i + 1; j < len; j++) {

if (list[j]

minT = i;

}

}

int tmp = list[minT];

list[minT] = list[i];

list[i] = tmp;

}

return list;

}Java泛型版

代码语言：javascript代码运行次数：0运行复制 public > T[] SelectionSort(T[] list) {

int len = list.length, minT;

for (int i = 0; i < len; i++) {

minT = i;

for (int j = i + 1; j < len; j++) {

if (list[j].compareTo(list[minT]) < 0) {

minT = i;

}

}

T tmp = list[minT];

list[minT] = list[i];

list[i] = tmp;

}

return list;

}1、时间复杂度：O(n2)O(n^2)O(n2) 2、空间复杂度：O(1)O(1)O(1) 3、非稳定排序

4、原地排序

☘️插入排序在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

伪代码

代码语言：javascript代码运行次数：0运行复制InsertionSort(A)

for j = 2 to A.length

key = A[j]

i = j-1

while i > 0 and A[i] > key

A[i+1] = A[i]

i = i -1

A[i+1] = keyJava代码

代码语言：javascript代码运行次数：0运行复制 public int[] InsertionSort(int list[]) {

int len = list.length;

for (int i = 1; i < len; i++) {

int tmp = list[i];

int j = i - 1;

// 将比插入元素值大的数往后移动

while (j >= 0 && list[j] > tmp) {

list[j + 1] = list[j];

j--;

}

// 插入元素

list[j + 1] = tmp;

}

return list;

}Java泛型版

代码语言：javascript代码运行次数：0运行复制 public > T[] InsertionSort(T list[]) {

int len = list.length;

for (int i = 1; i < len; i++) {

T tmp = list[i];

int j = i - 1;

// 将比插入元素值大的数往后移动

while (j >= 0 && list[j].compareTo(tmp) > 0) {

list[j + 1] = list[j];

j--;

}

// 插入元素

list[j + 1] = tmp;

}

return list;

}1、时间复杂度：O(n2)O(n^2)O(n2) 2、空间复杂度：O(1)O(1)O(1) 3、稳定排序

4、原地排序

🍀 O(n∗logN)O(n*logN)O(n∗logN)的排序算法☘️希尔排序在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。 然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。

假如待排序数组基本有序，使用插入排序更有效。

伪代码

代码语言：javascript代码运行次数：0运行复制ShellSort(A)

for path=0 to length_dlta

for i=path to n //一趟分段直接插入排序

temp = data[i]

j=i-path

while j>=0 and temp

data[j+path]=data[j]

j-=path

data[j+path]=tempJava代码

代码语言：javascript代码运行次数：0运行复制 private int[] ShellSort(int[] arr) {

int len = arr.length;

for (int d = len / 2;d>0;d /= 2){ //d：增量

for (int i = d; i < len; i++){

//i:代表即将插入的元素角标，作为每一组比较数据的最后一个元素角标

//j:代表与i同一组的数组元素角标

for (int j = i-d; j>=0; j-=d){ //在此处-d 为了避免下面数组角标越界

if (arr[j] > arr[j + d]) {// j+d 代表即将插入的元素所在的角标

//符合条件，插入元素（交换位置）

int temp = arr[j];

arr[j] = arr[j + d];

arr[j + d] = temp;

}

}

}

}

return arr;

}1、时间复杂度：O(nlogN)O(nlogN)O(nlogN) - O(n2)O(n^2)O(n2)，平均为O(n1.5)O(n^{1.5})O(n1.5) 2、空间复杂度：O(1)

3、非稳定排序

4、原地排序

☘️归并排序归并算法是分治思想一个经典应用。 将大的数组一直分割，直到数组的大小为 1，此时只有一个元素，那么该数组就是有序的了，之后再把两个数组大小为1的合并成一个大小为2的，再把两个大小为2的合并成4的 ….. 直到全部小的数组合并起来。

归并排序的分治思想

分解：分解待排序的n个元素的序列成各具 n/2 个元素的子序列解决：使用归并排序递归地排序子序列合并：合并两个已经排序的子序列以产生已排序的答案。伪代码

代码语言：javascript代码运行次数：0运行复制Merge(A, p, q, r)

n1 = q-p+1

n2 = r-q

//let L[1....n1+1] and R[1....n2+1] be new arrays

for i =1 to n1

L[i] = A[p+i-1]

for j=1 to n2

R[j] = A[q+j]

L[n1+1] = ∞

L[n2+1] = ∞

i=1

j=1

for k =p to r

if L[i]<=R[j]

A[k] = L[i]

i = i + 1

else

A[k]=R[j]

j = j+1

MergeSort(A,p,r)

if p < r

q = ⌊(p+r)/2⌋ //向下取整

MergeSort(A, p, q)

MergeSort(A, q+1, r)

Merge(A, p, q, r)Java代码

代码语言：javascript代码运行次数：0运行复制 public int[] MergeSort(int list[]) {

int tmp[] = new int[list.length]; //在排序前，先建好一个长度等于原数组长度的临时数组，避免递归中频繁开辟空间

MergeSort(list, 0, list.length - 1, tmp);

return list;

}

public void MergeSort(int[] list, int l, int r, int tmp[]) {

if (l < r) {

int mid = (l + r) / 2;

MergeSort(list, l, mid, tmp);

MergeSort(list, mid + 1, r, tmp);

Merge(list, l, mid, r, tmp);

}

}

void Merge(int list[], int l, int mid, int r, int tmp[]) {

int i = l; //左序列指针

int j = mid + 1; //右序列指针

int t = 0; //临时数组指针

while (i <= mid && j <= r) {

if (list[i] <= list[j]) {

tmp[t++] = list[i++];

} else {

tmp[t++] = list[j++];

}

}

while (i <= mid) { //将左边剩余元素填充进temp中

tmp[t++] = list[i++];

}

while (j <= r) { //将右序列剩余元素填充进temp中

tmp[t++] = list[j++];

}

t = 0;

//将temp中的元素全部拷贝到原数组中

while (l <= r) {

list[l++] = tmp[t++];

}

}1、时间复杂度：O(nlogN)O(nlogN)O(nlogN) 2、空间复杂度：O(n)O(n)O(n)

3、稳定排序

4、非原地排序

☘️堆排序堆的特点就是堆顶的元素是一个最值，大顶堆的堆顶是最大值，小顶堆则是最小值。 建立大顶堆； 拿掉堆顶的元素，重新构建堆； 拿掉堆顶元素，重新构建堆。。。 等到堆剩余的元素只有一个的时候，此时的数组就是有序的了。

伪代码

代码语言：javascript代码运行次数：0运行复制HeapSort(A)

BuildMaxHeap(A)

for i = A.length downto 2

exchange A[1] with A[i]

A.heap-size = A.heap-size - 1

MaxHeapify(A, 1)

// 建立大顶堆

BuildMaxHeap(A)

A.heap-size = A.length

for i = int(A.length / 2) downto 1

MaxHeapify(A, i)

//维护堆

MaxHeapify(A, i)

l = LEFT(i)

r = RIGHT(i)

if l <= A.heap-size and A[l] > A[i]

largest = l

else largest = i

if r <= A.heap-size and A[r] > A[largest]

largest = r

if largest <> i

exchange A[i] with A[largest]

MaxHeapify(A, largest)Java代码

代码语言：javascript代码运行次数：0运行复制 public int[] HeapSort(int list[]) {

BuildMaxHeap(list);

for (int i = list.length - 1; i >= 0; i--) {

int tmp = list[0];

list[0] = list[i];

list[i] = tmp;

MaxHeapify(list, 0, i);

}

return list;

}

public void BuildMaxHeap(int list[]) {

// 构建大顶堆

int heapSize = list.length;

for (int i = (heapSize / 2); i >= 0; i--) {

MaxHeapify(list, i, heapSize);

}

}

public void MaxHeapify(int list[], int i, int heapSize) {

// 维护堆

int l = LEFT(i);

int r = RIGHT(i);

int largest;

if (l <= heapSize - 1 && list[l] > list[i]) {

largest = l;

} else {

largest = i;

}

if (r <= heapSize - 1 && list[r] > list[largest]) {

largest = r;

}

if (largest != i) {

int tmp = list[i];

list[i] = list[largest];

list[largest] = tmp;

MaxHeapify(list, largest, heapSize);

}

}

public int PARENT(int i) {

return (i - 1) / 2;

}

public int LEFT(int i) {

return 2 * i + 1;

}

public int RIGHT(int i) {

return 2 * i + 2;

}1、时间复杂度：O(nlogN)O(nlogN)O(nlogN) 2、空间复杂度：O(1)O(1)O(1)

3、非稳定排序

4、原地排序

☘️快速排序同样是分治思想。 先从数列中取出一个数作为key值； 将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边； 对左右两个小数列重复第二步，直至各区间只有1个数。

伪代码

代码语言：javascript代码运行次数：0运行复制QuickSort(A, p, r)

if p < r

q = Partition(A,p,r）

QuickSort(A,p,q-1)

QuickSort(A,q+1,r)

Partition(A, p, r)

x = A[r]

i = p-1

for j = p to r-1

if A[j] <= x

i = i + 1

exchange A[i] with A[j]

exchange A[i+1] with A[r]

return i + 1Java代码

代码语言：javascript代码运行次数：0运行复制 public int[] QuickSort(int list[]) {

QuickSort(list, 0, list.length - 1);

return list;

}

public void QuickSort(int list[], int l, int r) {

if (l < r) {

int mid = Partition(list, l, r);

QuickSort(list, l, mid - 1);

QuickSort(list, mid + 1, r);

}

}

public int Partition(int list[], int l, int r) {

int x = list[r];

int i = l - 1;

for (int j = l; j <= r - 1; j++) {

if (list[j] <= x) {

i = i + 1;

int tmp = list[i];

list[i] = list[j];

list[j] = tmp;

}

}

int tmp = list[i + 1];

list[i + 1] = list[r];

list[r] = tmp;

return i + 1;

}1、时间复杂度：O(nlogN)O(nlogN)O(nlogN) 2、空间复杂度：O(logN)O(logN)O(logN) 3、非稳定排序

4、原地排序

🍀O(n+k)O(n+k)O(n+k)的排序算法、非比较排序☘️计数排序把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如 temp[i] = n, 表示元素 i 一共出现了 n 次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来是数据是有序的。

计数排序比较适用于待排序数组中最大值和最小值相差不大的排序。

伪代码

代码语言：javascript代码运行次数：0运行复制CountingSort(A,B,k)

let C[0..k] be a new array

for i = 0 to k //后面需要使用数组C来存储A中各元素的出现次数，所以需要清零操作

C[i] = 0

for j = 1 to A.length

C[A[j]] = C[A[j]] + 1 //统计A中各元素的出现次数存储在C中，C中下标为A中的元素值，与其对应的数组元素为出现次数，如C[1] = 0，即为“1”在A中的出现次数为0

for i = 1 to k

C[i] = C[i] + C[i-1] //计算A中小于等于i的一共有多少个，方便此后将i放在数组B中正确的位置上

for j = A.length downto 1

B[C[A[j]]] = A[j] //使用A中元素A[j]的出现次数作为B中的下标，把每个元素放在B中适当的位置

C[A[j]] = C[A[j]] -1 //在B中放入一个元素，与其对应C中出现的次数-1。这样，当遇到下一个等于A[j]的输入元素时，该元素可以被直接放到B中A[j]的前一位置上Java代码

代码语言：javascript代码运行次数：0运行复制 public int[] CountingSort(int list[]) {

int maxNum = Arrays.stream(list).max().getAsInt();

CountingSort(list, maxNum);

return list;

}

public void CountingSort(int list[], int maxNum) {

int tmp[] = new int[maxNum + 1];

int res[] = new int[list.length];

for (int item : list) {

tmp[item]++;

}

for (int i = 1; i < tmp.length; i++) {

tmp[i] += tmp[i - 1];

}

for (int i = list.length - 1; i >= 0; i--) {

// 数组下标从0开始，此处减1

res[tmp[list[i]]-1] = list[i];

tmp[list[i]]--;

}

}1、时间复杂度：O(n+k)O(n+k)O(n+k) ，K：建立的计数数组长度 2、空间复杂度：O(n+k)O(n+k)O(n+k)

3、稳定排序

4、非原地排序

☘️基数排序先以个位数的大小来对数据进行排序，接着以十位数的大小来多数进行排序，接着以百位数的大小。。。 排到最后，就是一组有序的元素了。

伪代码

代码语言：javascript代码运行次数：0运行复制RADIXSORT(A,d) // d:最高位数

for i = 1 to d

use a stable sort to sort array A on digit i // 从个位数至高位数依次重复排序Java代码

代码语言：javascript代码运行次数：0运行复制 public int[] RadixSort(int list[]) {

int maxNum = Arrays.stream(list).max().getAsInt();

int d = 0;

while(maxNum!=0) {

maxNum /=10;

d++;

}

RadixSort(list,d);

return list;

}

public void RadixSort(int list[], int d) {

int[] res = new int[list.length];//结果数组

int[] tmp = new int[10];//计数数组，范围为每位上的取值范围0-9

//一个十进制数m，它的个位数是m/1%10，十位数是m/10%10,百位数是m/100%10

for(int i=0;i

int division = (int)Math.pow(10, i);//取个位::/1 十位:/10 百位:/100中的基本划分点

for(int j=0;j

int num = list[j]/division%10;//取个位 十位 或百位上的数，每轮由此位置上的数大小进行计数排序

tmp[num]=tmp[num]+1;//进行计数排序中计数数组的更新

}

//计数排序中计数数组count的累加，保证稳定性

for(int m=1;m

tmp[m]=tmp[m]+tmp[m-1];

}

//计数排序中逆序遍历原数组A，根据累加后的数组count将A中每个元素正确填入result中正确的位置中

for(int j=list.length-1;j>=0;j--) {

int num = list[j]/division%10;

res[tmp[num]-1]=list[j];

tmp[num]=tmp[num]-1;

}

//将数组A更新为数组B

for(int j=0;j

list[j]=res[j];

}

//将数组C清零，进行下一轮的循环

for(int j=0;j

tmp[j]=0;

}

}

}1、时间复杂度：O(n+k)O(n+k)O(n+k) ，K：建立的计数数组长度 2、空间复杂度：O(n+k)O(n+k)O(n+k)

3、稳定排序

4、非原地排序

☘️桶排序把最大值和最小值之间的数进行瓜分，例如分成 10 个区间，10个区间对应10个桶，我们把各元素放到对应区间的桶中去，再对每个桶中的数进行排序，对桶中元素排序可采用其他排序方法。每个桶排序后再合并起来形成有序数组。

伪代码

代码语言：javascript代码运行次数：0运行复制BucketSort(A)

n = A.length

let B[0...n-1] be a new array

for i = 0 to n-1

b[i]=0

//make B an empty list

for i =1 to n

insert A[i] into list B[(int)nA[i]]

for i =0 to n-1

sort list B[i] with insertion sort

concatenate hte lists B[0...n-1] together in orderJava代码

代码语言：javascript代码运行次数：0运行复制 class LinkedNode {

public int value;

public LinkedNode next;

public LinkedNode(int value) {

this.value = value;

}

}

public int[] BucketSort(int list[]) {

int length = list.length;

LinkedNode[] bucket = new LinkedNode[length]; // 桶的个数等于length

int max = list[0]; // 求max

for (int i = 1; i < list.length; i++) {

if (list[i] > max) {

max = list[i];

}

}

// 入桶

for (int i = 0; i < length; i++) {

int value = list[i]; // 扫描每个元素

int hash = hash(list[i], max, length); // 桶的下标

if (bucket[hash] == null) {

bucket[hash] = new LinkedNode(value); // 初始化链表

} else {

insertInto(value, bucket[hash], bucket, hash); // 插入链表

}

}

int k = 0; // 记录数组下标

// 出桶，回填arr

for (LinkedNode node : bucket) {

if (node != null) {

while (node != null) {

list[k++] = node.value;

node = node.next;

}

}

}

return list;

}

private int hash(int element, int max, int length) {

return (element * length) / (max + 1);

}

private void insertInto(int value, LinkedNode head, LinkedNode[] bucket, int hash) {

LinkedNode newNode = new LinkedNode(value);

// 小于头节点，放在头上

if (value <= head.value) {

newNode.next = head;

// 替换头节点

bucket[hash] = newNode;

return;

}

// 往后找第一个比当前值大的节点，放在这个节点的前面

LinkedNode p = head;

LinkedNode pre = p;

while (p != null && value > p.value) {

pre = p;

p = p.next;

}

if (p == null) { // 跑到末尾了

pre.next = newNode;

} else { // 插入pre和p之间

pre.next = newNode;

newNode.next = p;

}

}1、时间复杂度：O(n+k)O(n+k)O(n+k) ，K：建立的计数数组长度 2、空间复杂度：O(n+k)O(n+k)O(n+k)

3、稳定排序

4、非原地排序