# Three sorting algorithms with O(N²) time complexity

2022-08-06 20:02:53

Compare elements of arrays,and decide whether to swap their positions.

• BUB - 冒泡排序
• SEL - 选择排序
• INS - 插入排序
• MER - 归并排序 (递归实现)
• QUI - 快速排序 (递归实现)
• R-Q - 随机快速排序 (递归实现)

• COU - 计数排序
• RAD - 基数排序

Let's break these sorting algorithms one by one.

## 冒泡排序

arr[0～N-1] 范围上：

arr[0] 和 arr[1],谁大谁来到1位置;

arr[1]和arr[2],谁大谁来到2位置;

[N-2]和arr[N-1],谁大谁来到N-1位置;

The whole process moves the largest element to the far right,That is, the largest element floats to the far right,像冒泡一样.

The figure shows the 1趟排序的过程.

A good picture is the one that moves by itself：

public class BubbleSort {

public static void main(String[] args) {
int[] arr = {18, 15, 13, 17, 6, 20, 15, 9};
sort(arr);
}

public static void sort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
//想要让0~i位置上有序,iStart at the maximum index position of the array,After every match1次,减1
for (int i = arr.length - 1; i > 0; i--) {
//0~i
//0~(i-1)
//0~(i-2)...
//0~1
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
System.out.println("0~" + i + "Location comparison results：" + Arrays.toString(arr));
}
}
}

第0Compare the results：[15, 13, 17, 6, 18, 15, 9, 20]

Compare and swap requires a to 常量 bounded time,我们称之为 $c$ .

Bubble Sort 中有两个嵌套循环.

$总迭代次数=（N-1）+（N-2）+ ... + 1 + 0 = N ×（N-1）/ 2$

$总时间= c × N ×（N-1）/ 2 = O（N²）$

## 选择排序

1. 在 [L ... N-1] Find the smallest item in the range X 的位置,
2. 用第 L 项交换X,
3. 将下限 L 增加1并重复步骤1直到 L = N-2.

Hand drawn selection sort process：

public class SelectionSort {

public static void main(String[] args) {
int[] arr = {18, 15, 13, 17, 6, 20, 15, 9};
sort(arr);
}

public static void sort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
//目的：找到最小值的位置,and sum the number at that positioni位置的数交换
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
minIndex = arr[j] > arr[minIndex] ? minIndex : j;
}
//找到最小值后,与i位置的数交换
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
System.out.println("第" + i + "~" + (arr.length - 1) + "The index of the minimum value at the position is " + minIndex + ",最小值为：" + arr[minIndex] + ",The result of this sorting：" + Arrays.toString(arr
));
}
}
}

第0~7The index of the minimum value at the position is 4,最小值为：18,The result of this sorting：[6, 15, 13, 17, 18, 20, 15, 9]

Summarize the process of selection sort：

arr[0～N-1]范围上,找到最小值所在的位置,然后把最小值交换到0位置.

arr[1～N-1]范围上,找到最小值所在的位置,然后把最小值交换到1位置.

arr[2～N-1]范围上,找到最小值所在的位置,然后把最小值交换到2位置.

arr[N-1～N-1]范围上,找到最小值位置,然后把最小值交换到N-1位置.

$总的常数操作数量 = a*(N²) + b*N + c (a、b、c都是常数)$

## 插入排序

1. 想让arr[0~0]上有序,这个范围只有一个数,当然是有序的;
2. 想让arr[0~1]上有序,所以从arr[1]开始往前看,如果 arr[1] < arr[0] ,就交换.否则什么也不做;

1. 想让arr[0~i]上有序,所以从arr[i]开始往前看,arr[i]这个数不停向左移动,一直移动到左边的数字不再比自己大,停止移动;
2. 最后一步,想让arr[0~N-1]上有序,arr[N-1]这个数不停向左移动,一直移动到左边的数字不再比自己大,停止移动.

$总的常数操作数量 = a*(N²) + b*N + c (a、b、c都是常数)$

So the time complexity of Insertion Sort is $O(N²)$ .

public class InsertionSort {
public static void main(String[] args) {
int[] arr = {18, 15, 13, 17, 6, 20, 15, 9};
sort(arr);
}

public static void sort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
//想让0~i位置上有序,从i位置往前看,Until the number on the left is no larger than himself,Stop looking left
for (int i = 1; i < arr.length; i++) {
//j=i表示从i位置开始,j--means looking forward
for (int j = i; j > 0; j--) {
if (arr[j] < arr[j - 1]) {
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
System.out.println("从" + i + "位置往前看,直到左边的数不比自己大,this result：" + Arrays.toString(arr));
}
}
}

从1位置往前看,直到左边的数不比自己大,this result：[15, 18, 13, 17, 6, 20, 15, 9]