排序在程序设计中是非常重要的，排序的种类很多，我在这里只列举了几种简单好用的排序。
冒泡排序
核心思想是贪心，这个算法应该是最经典的排序算法了，我第一次接触到的排序算法就是这个，当年学的时候还困扰了我好久。。其实挺简单的。
核心思想是：我们每次将相邻的元素进行比较，如果存在逆序\(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真香😄。不过把排序算法都自己尝试实现一遍，会对这些算法思想有更深刻的认识哦。
Comments | NOTHING