算法-排序详解[多语言实现]

一.冒泡排序

1.最常见的写法:

最基础的冒泡排序实现

c++:

1
2
3
4
5
6
7
8
9
10
void bubbleSort(vector<int>& arr) {
	int length = arr.size(); // 减少消耗
	for (int i = 0;i < length - 1;i++) {
		for (int j = 0;j < length - 1 - i;j++) {
			if (arr[j] > arr[j + 1]) {
				swap(arr[j], arr[j + 1]);
			}
		}
	}
}

JavaScript:

1
2
3
4
5
6
7
8
9
10
function bubbleSort(arr) {
    let length = arr.length
    for(let i=0;i<length-1;i++) {
        for(let j=0;j<length-1-i;j++) {
            if(arr[j]>arr[j+1]){
                [arr[j],arr[j+1]] = [arr[j+1],arr[j]]
            }
        }
    }
}

go:

1
2
3
4
5
6
7
8
9
10
func bubbleSort(arr []int) {
    length := len(arr)
    for i := 0;i<length-1;i++ {
        for j :=0;j<length-1-i;j++ {
            if(arr[j]>arr[j+1]) {
                arr[j],arr[j+1] = arr[j+1],arr[j]
            }
        }
    }
}

2.优化版：带标志位

通过标志位减少不必要的比较

c++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void bubbleSort(vector<int>& arr) {
	int length = arr.size(); // 避免后面使用重复开销
	bool flag = true;
	while (length > 1 && flag) {
		flag = false;
		for (int i = 0;i < length - 1;i++) {
			if (arr[i] > arr[i + 1]) {
				flag = true;
				swap(arr[i], arr[i + 1]);
			}
		}
		length--; // 采用--的操作,提高效率
	}
}

JavaScript:

1
2
3
4
5
6
7
8
9
10
11
12
13
function bubbleSort(arr) {
    let flag = true
    let length = arr.length
    while(length>1&&flag) {
        flag = false
        for(let i=0;i<length-1;i++) {
            if(arr[i]>arr[i+1]){
                [arr[i],arr[i+1]] = [arr[i+1],arr[i]]
            }
        }
        length--
    }
}

go:

1
2
3
4
5
6
7
8
9
10
11
12
13
func bubbleSort(arr []int) {
    length,flag := len(arr),true
    for length>1&&flag {
        flag = false
        for i := 0;i<length-1;i++ {
            if(arr[i]>arr[i+1]){
                flag = true
                arr[i],arr[i+1] = arr[i+1],arr[i]
            }
        }
        length--
    }
}

3.双向冒泡排序

从两侧依次冒泡

c++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void bubbleSort(vector<int>& arr) {
	int left = 0;
	int right = arr.size() - 1;
	bool flag = true;
	while (right > left && flag) {
		flag = false;
		for (int i = left;i < right;i++) {
			if (arr[i] > arr[i + 1]) {
				flag = true;
				swap(arr[i], arr[i + 1]);
			}
		}
		right--;
		for (int j = right;j > left;j++) {
			if (arr[j - 1] > arr[j]) {
				swap(arr[j - 1], arr[j]);
			}
		}
		left++;
	}
}

JavaScript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function bubbleSort(arr) {
    let left = 0
    let right = arr.length-1
    let flag = true
    while(right>left&&flag) {
        flag = false
        for(let i=left;i<right;i++) {
            if(arr[i]>arr[i+1]){
                flag = true
                [arr[i],arr[i+1]] = [arr[i+1],arr[i]]
            }
        }
        right--
        for(let j=right;j>left;j--) {
            if(arr[j]<arr[j-1]){
                flag = true
                [arr[j],arr[j-1]] = [arr[j-1],arr[j]]
            }
        }
        left++
    }
}

go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func bubbleSort(arr []int) {
    left,right,flag := 0,len(arr)-1,true
    for right>left&&flag {
        flag = false
        for i :=left;i<right;i++ {
            if(arr[i]>arr[i+1]) {
                flag = true
                arr[i],arr[i+1] = arr[i+1],arr[i]
            }
        }
        right--
        for j :=right;j>left;j-- {
            if(arr[j]<arr[j-1]) {
                flag = true
                arr[j],arr[j-1] = arr[j-1],arr[j]
            }
        }
        left++
    }
}

4.递归实现

通过递归的方式实现冒泡排序

c++:

1
2
3
4
5
void bubbleSort(vector<int>& arr,int length) { 
	if (length == 1)return;
	for (int i = 0;i < length - 1;i++)if (arr[i] > arr[i + 1]) swap(arr[i], arr[i + 1]);
	return bubbleSort(arr, length - 1);
}

JavaScript:

1
2
3
4
5
function bubbleSort(arr,length) {
    if(length===1)return;
    for(let i=0;i<length-1;i++)if(arr[i]>arr[i+1]) [arr[i],arr[i+1]] = [arr[i+1],arr[i]]
    return bubbleSort(arr,length-1)
}

go:

1
2
3
4
5
func bubbleSort(arr []int,length int) {
    if length==1 {return}
    for i:=0;i<length-1;i++ {if arr[i]>arr[i+1] {arr[i],arr[i+1] = arr[i+1],arr[i]}}
    bubbleSort(arr,length-1)
}

二.快速排序

1.最常见的写法:

使用递归实现快速排序，适合初学者理解

c++:

1

JavaScript:

1

go:

1

2.非递归写法（用栈模拟）

通过栈模拟递归逻辑

c++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
void QuickSort(vector<int>& arr) {
	// 栈实现这个快速排序的思路就是通过在栈中存储这个数组的临界边界
	int length = arr.size();
	if (length <= 1)return;
	//定义一个栈容器
	stack<pair<int, int>>Boundary;
	Boundary.push({ 0,length - 1 });
	while (!Boundary.empty()) {
		int left = Boundary.top().first; // 取出来这个栈中的数据
		int right = Boundary.top().second;
		Boundary.pop();
		if (right > left) {
			int middle = left + (right - left) / 2;
			int middlenumber = arr[middle];
			int leftnumber = left;
			int rightnumber = right;
			while (rightnumber >= leftnumber) {
				while (arr[leftnumber] < middlenumber)leftnumber++;
				while (arr[rightnumber] > middlenumber)rightnumber--;
				if (rightnumber >= leftnumber) {
					swap(arr[rightnumber], arr[leftnumber]);
					rightnumber--;
					leftnumber++;
				}
			}
			Boundary.push({ left,rightnumber });// 将两个区间的值压入栈中去
			Boundary.push({ leftnumber,right });
		}
	}
}

JavaScript:

1

go:

1

3.原地快速排序（双指针）

在数组中进行原地排序，节省额外空间

在这里我采用从中间位置为基准点(纯属个人习惯)

注:选择数组的中间元素作为基准，避免了选择第一个元素导致最坏情况（已排序数组）的问题。通过使用左右指针（leftnumber 和 rightnumber），分别从两端向中间扫描，找到不符合条件的元素并交换，直到指针交错。然后递归地对左右子数组进行排序，确保每次划分较为均匀，从而优化了排序性能，特别是在应对已排序或逆序数组时，减少了退化为 O(n2)O(n^2)O(n2) 的风险。

c++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 我的不是从第一个元素作为基准点,考虑到最坏的情况,已经排好序了,那么选择第一个是最坏的结果,所有我试着选择中间的节点
void QuickSort(vector<int>&arr, int left, int right) {// 在这里我采用的是从中间作为基准点,而不是书上的从第一个作为基准点,我认为书本上的做法不够最优,本身就多增加了一个内存用来存储第一个数据
	if (left >= right)return;// 最为递归退出的条件
	int targetnumber = arr[(left + right) / 2];// 选择中间元素作为基准
	int leftnumber = left;
	int rigthnumber = right;
	while (rigthnumber >= leftnumber) {
		while (arr[leftnumber] < targetnumber)leftnumber++;// 如果满足条件,小的在左边,就移动指针
		while (arr[rigthnumber] > targetnumber)rigthnumber--;// 如果满足条件,大的在右边,就移动指针
		if (rigthnumber > leftnumber) {// 如果最后还是没能移	动完指针的话,就说明需要交换一下顺序了
			swap(arr[leftnumber], arr[rigthnumber]);
			leftnumber++;
			rigthnumber--;
		}
		else if (rigthnumber == leftnumber)break;
	}
	if (left < rigthnumber) QuickSort(arr, left, rigthnumber);// 递归排序左右子数组
	if (leftnumber < right) QuickSort(arr, leftnumber, right);
}

JavaScript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function QuickSort(arr,left,right) {
    if(left>=right)return
    let middlenumber = arr[Math.floor((left + right)/2)]
    let leftnumber = left
    let rightnumber = right
    while(rightnumber >= leftnumber) {
        while(arr[leftnumber] < middlenumber) leftnumber++
        while(arr[rightnumber] > middlenumber) rightnumber--
        if(rightnumber >= leftnumber) {
            [arr[leftnumber],arr[rightnumber]] = [arr[rightnumber],arr[leftnumber]]
            leftnumber++
            rightnumber--
        }
    }
    QuickSort(arr,left,rightnumber)
    QuickSort(arr,leftnumber,right)
}

go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func QuickSort(arr []int,left int,right int) {
    if left>=right {return}
    middlenumber,leftnumber,rightnumber:=arr[(left+right)/2],left,right
    for rightnumber >=leftnumber {
        for arr[leftnumber] < middlenumber {leftnumber++}
        for arr[rightnumber] >middlenumber {rightnumber--}
        if rightnumber >= leftnumber {
            arr[leftnumber],arr[rightnumber] = arr[rightnumber],arr[leftnumber]
            leftnumber++
            rightnumber--
        }
    }
    QuickSort(arr,left,rightnumber)
    QuickSort(arr,leftnumber,right)
}

4.三路快排

适合处理包含大量重复元素的数组

三路快速排序（3-Way QuickSort）是快速排序的一个优化版本，适用于数组中有许多重复元素的情况。在标准的快速排序中，数组会被划分成两部分：小于基准和大于基准，而三路快速排序会将数组划分为三部分：小于基准、等于基准和大于基准。这种划分方法有助于减少重复元素的处理，提高效率。

使用场景：

三路快速排序特别适用于数组中有大量重复元素的情况，因为它能够更好地处理这些元素，避免了普通快速排序在处理重复元素时性能下降的情况。

划分三部分：

  • 小于基准的部分（left）

  • 等于基准的部分（middle）

  • 大于基准的部分（right）

    递归排序：只对小于基准和大于基准的部分进行递归，而对等于基准的部分不进行排序，因为它们已经是有序的。

性能分析：

  • 时间复杂度

    ：

    • 最优和平均情况：O(nlog⁡n)O(n \log n)O(nlogn)
    • 最坏情况：O(n2)O(n^2)O(n2)，当数组中有很多重复元素时，三路快速排序能避免重复元素导致的性能下降，因此它通常优于标准快速排序。

  • 空间复杂度：由于是递归实现，空间复杂度为 O(log⁡n)O(\log n)O(logn)（递归栈空间）。

c++:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void ThreeWayQuickSort(vector<int>&arr, int left, int right) {
	if (left >= right)return;// 递归退出条件
	int middle = (left + right) / 2;//取中间地位置
	int middlenumber = arr[middle];
	// 下面采用三个指针来表示
	int leftindex = left;
	int rightindex = right;
	int index = left;
	while (index <= right) {
		if (arr[index] < middlenumber) {
			swap(arr[index], arr[leftindex]);
			index++;
			leftindex++;
		}
		else if (arr[index] > middlenumber) {
			swap(arr[index], arr[rightindex]);
			rightindex--;
		}
		else {
			index++;// 对于等于中间值地数据,不做交换处理,就直接跳过
		}
	}
	ThreeWayQuickSort(arr, left, leftindex - 1);
	ThreeWayQuickSort(arr, rightindex + 1, right);
}

JavaScript:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function threeWayQuickSort(arr, left, right) {
    if (left >= right) return; 
    const middle = Math.floor((left + right) / 2); 
    const middlenumber = arr[middle];
    let leftIndex = left;
    let rightIndex = right;
    let index = left;
    while (index <= right) {
        if (arr[index] < middlenumber) {     
            [arr[index], arr[leftIndex]] = [arr[leftIndex], arr[index]];
            index++;
            leftIndex++;
        } else if (arr[index] > middlenumber) {
            [arr[index], arr[rightIndex]] = [arr[rightIndex], arr[index]];
            rightIndex--;
        } else {
            index++; 
        }
    }
    threeWayQuickSort(arr, left, leftIndex - 1);
    threeWayQuickSort(arr, rightIndex + 1, right);
}

go:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func threeWayQuickSort(arr []int, left, right int) {
	if left >= right {
		return
	}
	middle := (left + right) / 2
	middlenumber, leftIndex, rightIndex, index := arr[middle], left, right, left
	for index <= rightIndex {
		if arr[index] < middlenumber {
			arr[index], arr[leftIndex] = arr[leftIndex], arr[index]
			leftIndex++
			index++
		} else if arr[index] > middlenumber {
			arr[index], arr[rightIndex] = arr[rightIndex], arr[index]
			rightIndex--
		} else {
			index++
		}
	}
	threeWayQuickSort(arr, left, leftIndex-1)
	threeWayQuickSort(arr, rightIndex+1, right)
}

三.选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void SelectSort(datatype arr[]) {
	int length = length_arr;
	for (int i = 0;i < length;i++) {
		int nums = i;// 先保存好第i躺的数据i
		for (int k = i + 1;k < length;k++) {
			if (arr[k] < arr[nums]) {// 如果找到了比第nums还要小的数据,先保存好下标
				nums = k;
			}
		}
		if (nums != i) {// for循环完毕,如果nums还是i,说明后面的数据没有最小的了,也就是遍历完了
			datatype data = arr[i];// 交换最小值
			arr[i] = arr[nums];
			arr[nums] = data;
		}
	}
}

四.堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void Headadjust(datatype arr[], int length, int i) {
	int topnumber = i;// 表示的是这个二叉树的一个两个子树的父节点
	int leftnumber = 2 * i + 1;// 左子树
	int rightnumber = 2 * i + 2;// 右子树
	if (leftnumber<length && arr[leftnumber]>arr[topnumber]) {
	topnumber = leftnumber;
	HeapSortnums++;
	}
	if (rightnumber<length && arr[rightnumber]>arr[topnumber]) {
	topnumber = rightnumber;
	HeapSortnums++;
	}
	if (topnumber != i) {// 如果这个下标值改变的话,就说明这个树没有实现大堆化,进行交换数据
		datatype data = arr[topnumber];
		arr[topnumber] = arr[i];
		arr[i] = data;
		Headadjust(arr, length, topnumber);//进行递归,解决因为父亲节点的问题而引发的一系列问题导致下面已经排好大堆顺序因为父亲交换的缘故让下面的节点不在是大堆的排序状态
	}
}
void HeapSort(datatype arr[]) {// 堆排序的主要的函数部分
	int length = length_arr;
	for (int i = length / 2 - 1; i >= 0; i--) {//完全二叉树的叶子节点数量大约等于所有节点的一半,而叶子节点是可以看作是一个正确的堆的
		Headadjust(arr, length, i);
	}
	for (int i = length; i > 0; i--) {// 这个就是对数组进行排序了,从小到大
		datatype data = arr[0];
		arr[0] = arr[i];
		arr[i] = data;
		Headadjust(arr, i - 1, 0);
	}
}

五.插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
void InsertionSort(datatype arr[]) {
	int length = length_arr;int k;
	for (int i = 1;i < length;i++) {// 从第二个开始循环比较,避免出现数组越界
		if (arr[i] < arr[i - 1]) {
			datatype temp = arr[i];// 先暂存起来
			arr[i] = arr[i - 1];// 大的那个数先先后填补一下后面的小的数的值的地方
			for (k = i - 1;k>=0&&temp < arr[k];k--) {// 倒着往前面走,找到合适的地方插,还没有找到的话就是把当前的往后面移动
				arr[k + 1] = arr[k];// k可以处理边界问题,因为k为0的时候就结束循环
			}
			arr[k + 1] = temp;
		}
	}
}

六.折半插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void BinaryInsertionSort(datatype arr[]) {
	int length = length_arr;int k;
	for (int i = 1;i < length;i++) {// 从第二个开始循环比较,避免出现数组越界
		datatype temp = arr[i];// 先暂存起来
		int left = 0;
		int right = i - 1;
		while (right >= left) {// 二分查找,找到要插入的地方
			int middle = left + (right - left) / 2;
			if (temp >= arr[middle]) {
				left = middle + 1;
			}
			else {
				right = middle - 1;
			}
		}
		for (k = i - 1;k >= right+1 && temp < arr[k];k--) {// 倒着往前面走,找到合适的地方插,还没有找到的话就是把当前的往后面移动
			arr[k + 1] = arr[k];// k可以处理边界问题,因为k为0的时候就结束循环
		}
		arr[k + 1] = temp;
	}
}

七.希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void ShellSort(datatype arr[]) {
	int length = length_arr;int k;
	int opp = log(length) / log(2) - 1;
	int f = pow(2, opp) - 1;
		while (f >= 1) {// 对数据进行分组
			for (int i = f;i < length;i++) {// 从第二个开始循环比较,避免出现数组越界
				if (arr[i] < arr[i - f]) {
					datatype temp = arr[i];// 先暂存起来
					arr[i] = arr[i - f];// 大的那个数先先后填补一下后面的小的数的值的地方
					for (k = i - f;k >= 0 && temp < arr[k];k--) {// 倒着往前面走,找到合适的地方插,还没有找到的话就是把当前的往后面移动
						arr[k + f] = arr[k];// k可以处理边界问题,因为k为0的时候就结束循环
					}
					arr[k + f] = temp;
				}
			}
			opp--;
			f = pow(2, opp) - 1;
		}
}

八.归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void Merging(datatype arr[], datatype temparr[], int leftnumber, int middlebumber, int rightnumber) {
	// 使用指针类似的东西
	int left = leftnumber;// 这个代表的是左边的第一个数组的第一个元素所指向的下标索引
	int middle = middlebumber + 1;//这个代表的是左边的第二个数组的第一个元素所指向的下标索引
	int start = leftnumber;
	while (left != middlebumber + 1 && middle != rightnumber + 1) {
		if (arr[left] <= arr[middle]) {// 说明的就是左边的值比右边的值还要小
			temparr[start++] = arr[left++];
		}
		else {
			temparr[start++] = arr[middle++];
		}
	}
	while (left != middlebumber + 1) {// 说明左边的值还有,可是右边的值已经没有了
		temparr[start++] = arr[left++];
	}
	while (middle != rightnumber + 1) {// 说明右边的值还有,可是左边的值已经没有了
		temparr[start++] = arr[middle++];
	}
	for (int i = leftnumber;i <= rightnumber;i++) {
		arr[i] = temparr[i];
	}
}
void MergingSort(datatype arr[],datatype temparr[],int leftnumber,int rightnumber) {
	int middlenumber;// 划分为两个数组的关键之处为middlenumber,作为分割线
	if (rightnumber > leftnumber) {// 直到划分到只有一个数据为止
		middlenumber = (rightnumber + leftnumber) / 2;
		MergingSort(arr, temparr, leftnumber, middlenumber);// 递归左边的,直到只有一个数据为止
		MergingSort(arr, temparr, middlenumber+1, rightnumber);// 递归右边的
		Merging(arr, temparr, leftnumber, middlenumber, rightnumber);// 合并数组
	}
}

九.基数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
int maxdatabit(datatype arr[]) {// 返回最大位数
	int length = length_arr;
	datatype data = 0;// 寻找最大值
	int databit = 0;
	for (int i = 0;i < length;i++) {
		if (arr[i] > data) {
			data = arr[i];
		}
	}
	while (data) {// 寻找最大位数
		databit++;
		data /= 10;
	}
	return databit;// 返回最大的位数
}
void RadixSort(datatype arr[]) {
	int length = length_arr;
	int indexnubmer;//用来弄位数的
	int max_bit = maxdatabit(arr);// 获取最大的位数
	// 对这个数组进行基数排序
	for (int i = 0;i < max_bit;i++) { // 对相应的每一个位数进行排序
		int collectdata[10] = { 0 };// 用来计数[记录数据的个数
		int temparr[length_arr];
		for (int j = 0;j < length;j++) { // 对相应的位数的数据进行计数
			int index = (arr[j] / indexnubmer) % 10;
			collectdata[index]++;
		}
		// 将计数器转为累积计数
		for (int j = 1; j < 10; j++) {
			collectdata[j] += collectdata[j - 1];
		}
		// 将数据按当前位数排序到临时数组
		for (int j = length - 1; j >= 0; j--) { // 倒序遍历保持稳定性
			int index = (arr[j] / indexnubmer) % 10;
			temparr[collectdata[index] - 1] = arr[j];
			collectdata[index]--;
		}
		for (int k = 0;k < length;k++) { // 更新数组,对数组进行对位数的排序
			arr[k] = temparr[k];
		}
		delete[] temparr;
		indexnubmer = indexnubmer * 10;
	}
}