c++十大排序算法学习笔记（一）

1. 学前预备知识总结 （1） c++中怎样生成一定范围的随机数

//举个例子 生成0~99的随机数

#include 
#include 
#include 
#define random(x) rand()%(x)    //可以定义为这种形式，也可以直接用 rand()%100
using namespace std;

int main()
{
	srand((int)time(0));  // 产生随机种子  把0换成NULL也行
	for (int i = 0; i < 10; i++)
	{
		cout << random(100) << " ";
	}
	return 0;
}

note： 本章所有代码都是在VS 2022中运行，在此IDE中

Ctrl - K 启动组合键，再按 Ctrl - C 触发组合键批量注释 
取消注释的话，选中代码之后Ctrl - K 启动组合键，再按 Ctrl - U 触发组合键 取消批量注释

（2）求取两个数中的最大值c++中提供max函数

必须包含      #include          int a, b ;      max(a,b)    求a， b 中的最大值。

（3）开辟一个新的数组并初始化大小 ，在c++中可以这样

int n = 10;
//构造n个elem元素可以这样；
vector arr（n,elem）;

//初始化一个大小为n的数组
vector arr1(n,0); // 等同于vector arr1(n);  不写0默认为0;

//或者
vector arr2;
arr.resize(n);

//vector还可以拷贝
vector arr3(arr1.begin(), arr1.end());  // 拷贝范围为左闭右开[a,b)

(4) 排序检测用的   对数器

#include 
using namespace std;
#include 
#include
#include 
#include
#include  //要调用time()，需要加入头文件< ctime >
#define random_int_1(a,b)       (rand()%(b - a) + a )           //取得[a,b)的随机整数
#define random_int_2(a,b)       ((rand()%(b-a+1))+ a)            //取得[a,b]的随机整数

void comparator(vector& arr) {
	sort(arr.begin(), arr.end());   // 系统自带的的排序函数，必然正确的
}


vector generateRandomArray(int maxSize, int maxValue) {
	srand((int)time(0));  //利用系统时钟，产生不同的随机数种子,把0换成NULL也行
	int number = random_int_1(0, maxSize+1);
	vector arr(number);
	for (int i = 0; i < arr.size(); i++) {
		 //arr[i] = int(random_int_1(0, maxSize + 1) - random_int_1(0, maxSize ));  //可以产生负整数  这里先不用
		 arr[i] = int(random_int_1(0, maxSize + 1));
	}
	return arr;
}

void test() {
	int testTime = 5000;    //测试的次数
	int maxSize = 100;      // 数组的最大大小
	int maxValue = 100;     //数组的最大值
	bool succeed = true;
	for (int i = 0; i < testTime; i++) {
		vector arr1 = generateRandomArray(maxSize, maxValue);
		vector arr2;
		arr2.resize(arr1.size());
		copy(arr1.begin(), arr1.end(), arr2.begin());    
        //上边三行也可以改为： vector arr2(arr1.begin(), arr1.end());
		bubblesort(arr1,0,arr1.size()-1);//你自己写的排序算法
		comparator(arr2);
		if (arr1 != arr2) {
			succeed = false;
			break;
		}
	}
	if (succeed == true) {
		cout << "Nice!" << endl;
	}
	else {
		cout << "Fuck!!" << endl;
	}
}

如果你写的排序函数正确  ，就返回输出Nice！   否者输出Fuck！

二、 最简单的冒泡排序算法

#include 
using namespace std;
#include 
#include
#include 

//有三种
//方法一：经典
void bubblesort(vector &arr){
    int n = arr.szie();
    if(n < 2) return;
    for(int i = n-1; i>0;i--){
        for(int j = 0; j arr[j+1]){
                swap(arr[j], arr[j+1]);
            }
        }
    }
}


//方法二： 递归
void bublesort1(vector &arr, int n){
    if(n<2) return;   //递归结束的条件
    for(int i = 0; i arr[i+1]){
            swap(arr[i], arr[i+1]);
        }
    }
    bubblesort1(arr, n-1);
}

//方法三： 优化方法
void bubblesort2(vector& arr) {
	int n = arr.size();
	if (n < 2) return;
	for (int i = n - 1; i > 0; i--) {   //一共进行n-1次比较
		bool flag = false;
		for (int a = 0; a < arr.size(); a++) { //测试用，看看进行了几次排序
			cout << arr[a] << "、";
		}
		cout << endl;
		for (int j = 0; j < i; j++) {    //第一次，进行n-1次，然后是n-1-1，以此类推
			if (arr[j] > arr[j + 1]) {
				swap(arr[j], arr[j + 1]);
				flag = true;
			}
		}
		if (flag == false) return;
	}
}


void print(vector& arr) {
	for (int i = 0; i < arr.size(); i++) {
		cout << arr[i] << endl;
	}
}

void main(){
    vector arr = {9, 5, 8, 2, 10, 3, 6, 18 ,4};
    bubblesort(arr);
    print(arr) 
    bubblesort1(arr,arr.szie()-1);
    print(arr) 
    bubblesort2(arr);
    print(arr) 
    return 0;
}

三、 选择排序

选择排序就是，从头到尾扫描序列，找出最小的一个元素，和第一个元素交换，接着从剩下的元素中继续这种选择和交换方式，最终得到一个有序的序列。

#include 
using namespace std;
#include 
#include
#include 

//1、 经典
void selectsort(vector &arr){
    int n = arr.size()-1;
    for(int i = 0; i& arr, int i) {
	int n = arr.size();
	if (i >= n) return;
	int minIndex = i;
	for (int j = minIndex + 1; j < n; j++) {
		if (arr[j] < arr[minIndex]) {
			minIndex = j;
		}
	}
	swap(arr[i], arr[minIndex]);
	selectsort2(arr, i + 1);
} 

//3、优化 （双指针）
void selectsort3(vector& arr) {
	int n = arr.size();
	if (n < 2) return;
	int left = 0;
	int right = n - 1;
	
	while (left < right) {
		int min = left;
		int max = left;
		for (int i = left; i <= right; i++) {
			if (arr[i] < arr[min]) min = i;     //选出整个数组中最小的数的下角标
			if (arr[i] > arr[max]) max = i;     //选出整个数组中最大数的下角标
		}
		if (arr[min] != arr[left])  swap(arr[min], arr[left]);    //(1)
		if (max == left)            max = min;                    //(2)
		if (arr[max] != arr[right]) swap(arr[max], arr[right]);   //(3)
		left++;
		right--;
		
	}
}

本节先记录冒泡排序和选择排序，其它排序看下一章节。