排序在程序设计中是非常重要的,排序的种类很多,我在这里只列举了几种简单好用的排序。

冒泡排序

核心思想是贪心,这个算法应该是最经典的排序算法了,我第一次接触到的排序算法就是这个,当年学的时候还困扰了我好久。。其实挺简单的。

核心思想是:我们每次将相邻的元素进行比较,如果存在逆序\(i<j \,\,\&\& a\left[ i \right] > a\left[ j \right]\)就进行交换,第一趟完成之后,最大的元素就位,第\(n\)趟之后,第 \(n\) 大的元素就位。

代码:

#include<iostream>
using namespace std;

int arr[100];

void swap(int & a, int & b) {
	int t = a;
	a = b;
	b = t;
}

void bubble_sort(int len) {
	for(int i = len - 1 ; i >= 0 ; --i) {
		for(int j = 0 ; j < i ; ++j) {
			if(arr[j] > arr[j+1]) {  //相邻比较
				swap(arr[j] , arr[j+1]);
			}
		}
	}
}

int main() {
	
	for(int i = 0 ; i <= 10 ; ++i) {
		arr[i] = 10 - i;
	}
	
	bubble_sort(10);
	
	for(int i = 0 ; i < 10 ; ++i)
		cout << arr[i] << endl;
	return 0; 	
} 

选择排序

核心思想是减治,将序列分为左右两个部分,左边部分为乱序,右边部分为有序,每次将左边序列中的最大值与右边序列的前一个元素进行交换,反复迭代之后,左边序列为空,右边序列即为整个序列。

代码:

#include<iostream>
using namespace std;
int arr[100];
void swap(int & a , int & b) {
	int t = a;
	a = b;
	b = t;
}
void selection_sort(int len) {
	int t;
	for(int i = len ; i >= 0 ; --i) {
		int t = i;  //将最后一个设置为最大元素 
		for(int j = 0 ; j < i ; ++j) { //在前面寻找最大元素 
			if(arr[j] > arr[t]) {
				t = j; 
			}
		}		
		if(t != i) {
			swap(arr[t], arr[i]);
		}
	}	
}
int main() {	
	for(int i = 0 ; i < 10 ; i++) {
		arr[i] = 10 - i;
	}	
	selection_sort(10);	
	for(int i = 0 ; i < 10 ; ++i) {
		cout << arr[i] << endl;
	}
} 

堆排序

在讲优先级队列的时候说过,使用堆这种数据结构,可以仅用\(O\left( \log n \right) \)的时间就可以得到最大或最小的元素,所以我们可以使用堆来维护无序的部分,每次取出最大的元素插入到有序部分。(这里我为了简单没有建堆。。而是直接用的priority_queue,c语言里面没有这种东西还是得自己写)

#include<iostream>
#include<queue>
using namespace std;
int arr[100];
void heap_sort(int len) {
	priority_queue<int> PQ; 	
	for(int i = 0 ; i < len ; ++i) {
		PQ.push(arr[i]);
	}
	
	for(int i = len - 1 ; i >= 0 ; --i) {
		arr[i] = PQ.top();
		PQ.pop();
	}
} 
int main() {
	for(int i = 0 ; i < 10 ; ++i) {
		arr[i] = 10 - i;
	}	
	heap_sort(10);	
	for(int i = 0 ; i < 10 ; ++i) {
		cout << arr[i] << endl;
	}		
}
 

插入排序

插入排序也是基于减而治之的思想,左边序列为有序部分,右边序列为无序部分,我们每次取出右边的第一个元素,插入到左边序列中,使其仍然有序。一般我们认为,插入排序虽然时间复杂度和选择排序一样均为\(O\left( n^2 \right) \),但插入排序的好处是我们可以对数据进行在线处理,我们不必每次都需要一个完整的序列,而是来一个数据,我们处理一个数据,这种支持在线处理的算法是非常重要的。

代码:

#include<iostream>
#include<stdlib.h> 
using namespace std;
int arr[100];
void insertion_sort(int len) {	
	for(int i = 1; i < len ; ++i) {
		int tmp = arr[i];  //插入的值 
		
		for(int j = 0 ; j < i ; ++j) {    //从有序的地方开始找 
			if(tmp < arr[j]) {  //找到插入的地方 
				for(int k = i; k > j ; --k)  {  //挪动元素开始插入 
					arr[k] = arr[k - 1];	
				}				
				arr[j] = tmp; //找到合适的位置了,进行插入
				break;
			}		
		}	
	} 
}
int main() {
	for(int i = 0 ; i < 20 ; ++i) 
		arr[i] = rand() % 100 + 1;
	
	cout << "原始" << endl;	
	for(int i = 0 ; i < 20 ; ++i) 
		cout << arr[i] << endl;
	
	insertion_sort(20); 
	cout << "插入" << endl; 
	for(int i = 0 ; i < 20 ; ++i) 
		cout << arr[i] << endl;
	
	return 0;
} 

PS: 插入排序的代码一不小心就会写错。。一定要细心。。

归并排序

和前面的几种排序算法的核心思想有略微的区别,归并排序的核心思想时分治,将一个大问题分解为若干个小问题,然后同时处理(一般用递归实现)。如果我们需要对一个序列进行排序,我们只需要对其左边部分进行排序,再对右边部分进行排序,排序完成后,我们将其合并就完成了。如果我们需要对其左边部分进行排序,我们只需要将左边序列的左边序列进行排序......然后就递归下去了,直到问题被转化成每一个序列都是一个单独的元素,那我们就相当于排好序了:

我们只需要再进行归并就好了,我们使用二路归并来进行处理:

当我们需要合并两个有序序列的时候,我们只需要比较它们中的首元素,谁小就将其放入一个新的序列中,这个思路应该不难理解,代码实现会有一点点麻烦。

代码:

#include<iostream>
using namespace std;
int arr[10005];
int b[10005];
void mergesort(int L, int R) {
	if(L == R) return;
	
	int mid = (L + R) >> 1;  //相当于除以2,找到中点位置 
	mergesort(L, mid);   //左边进行排序 
	mergesort(mid + 1, R);   //右边进行排序 
	
	int Ldx = L;
	int Rdx = mid + 1;
	int New_dx = L;
	
	while(Ldx <= mid && Rdx <= R) {   //进行归并,谁小就将谁加入新的序列中 
		if(arr[Ldx] < arr[Rdx]) {
			b[New_dx++] = arr[Ldx++];
		} else {
			b[New_dx++] = arr[Rdx++];
		}
	}
	
	while(Ldx <= mid) {   //上一轮循环如果没有加完,就将数据全部存入新序列 
		b[New_dx++] = arr[Ldx++];
	}
	
	while(Rdx <= R) {
		b[New_dx++] = arr[Rdx++];
	}
	
	for(int i = L ; i <= R ; ++i) {  //最后将新序列还原到原序列中 
		arr[i] = b[i];
	}
		
}
	
int main()  {
	
	for(int i = 0 ; i < 10 ; ++i) {
		arr[i] = 10 - i;
	}
	
	mergesort(0, 9); //左右都是闭区间 
	
	for(int i = 0 ; i < 10 ; ++i) {
		cout << arr[i] << endl;
	}
	
}

时间复杂度为\(O\left( n\log n \right) \)

快速排序

快速排序应该是用的最多的一种排序了,STL库中的sort函数就是快速排序,快速排序的思想是:我们每次都选定一个界限,根据这个界限,我们将序列调整为左边的元素都比他小,右边的元素都比他大:

调整完成后,我们再对左右两边的序列进行同样的处理,直到序列有序。关于界限的选定,我是随机取的,应该有更好的办法,但是很麻烦。。

代码:

#include<iostream>
#include<stdlib.h>
using namespace std;
int arr[10005];
void swap(int & a, int & b) {
	int t = a; 
	a = b;
	b = t;
}
void quicksort(int L, int R) {
	if(L > R) return;
	int Ldx = L;
	int Rdx = R;     
 	int bound = arr[rand() % (R - L + 1) + L];  //在L和R之间,随机选择一个值作为界桩
	
	while(Ldx <= Rdx) {
		while(arr[Ldx] < bound) {   //这一轮循环迭代完后,ldx指向的是大于或等于界桩的数,需要被安排一下 
			Ldx ++;       
		}
		while(arr[Rdx] > bound) {   //这一轮循环迭代完后,rdx指向的是小于或等于界桩的数,也需要被安排一下 
			Rdx --;          //因为我们要保证左边的数都比界桩要小,右边的数都比界桩要大。 
		}
		
		if(Ldx <= Rdx) {        //如果是在范围内,我们将其进行调换。 
			swap(arr[Ldx++], arr[Rdx--]);
		}
		
	}
    //大循环迭代完后,Rdx会指向mid左边一个,ldx会指向mid右边的一个,不信你可以验证一下	
	quicksort(L, Rdx);        //然后我们在对左边的数据进行处理 
	quicksort(Ldx, R);       //对右边的数据进行处理 
}
int main () {
	for(int i = 0 ; i < 10 ; ++i) {
		arr[i] = 10 - i;
	}
	
	quicksort(0, 9);
	
	for(int i = 0 ; i < 10 ; ++i){
		cout << arr[i] << endl;
	} 
	return 0;	
} 

如果你问我在刷题的时候我会用什么排序,我一定会说std::sort真香😄。不过把排序算法都自己尝试实现一遍,会对这些算法思想有更深刻的认识哦。

立志成为一名攻城狮
最后更新于 2023-03-28