数据结构与算法—排序算法篇

//选择排序
void Select_Sort(int a[],int n) {	//第一个参数是数组，第二个参数是 元素个数
	for (int i = 0; i  a[j]) {	//a[i] > a[j] 就是升序 ，

//冒泡排序
void bubble_sort(int a[], int n) {
	for (int i = 0; i  a[j]) {	//  > 升序， 

//改进冒泡排序
void bubble_sort1(int a[], int n) {
	for (int i = 0; i  a[j]) {	//  > 升序， 

//插入排序
void insert_sort(int a[],int n) {
	for (int i = 1; i = 0;j--) {
			if (a[j] > a[index]) {	// > 升序   

int h = 1;
while(h 

//希尔排序
void shell_sort(int a[],int n) {	//1、数组首地址  2、数组长度
	//计算步长
	int jmp = 1;
	while (jmp >1) {	 // jmp >1 一定程度上等价于 /2
		jmp = jmp * 2 + 1;
	}

	//插入排序
	int tmp;	//记录当前待插入元素
	int j;		//定位比较的元素
	while (jmp != 0) {
		for (int i = jmp; i = 0 && tmp 

//归并排序
//2、归并 vector
void Merge(int a[], int left, int mid, int right) {
	vector vt;		//定义一个临时动态数组
	vt.resize(right-left+1);	//指定vector尺寸
	int k = 0;
	int pl = left;
	int pr = mid + 1;

	//同时成立时，两个索引的值进行比较
	while (pl  目标
	for (int i = left, j = 0; i 

//快速排序——递归
void quick_sort(int a[],int size, int left, int right) { //1、数组首地址 2、左边界 3、右边界	

	if (left >= right) {
		return;
	}
	//以a[left] 为基准
	int le = left+1;
	int ri = right;

	while(true){

		cout 右，取大于
		while (le = a[left]) {
				break;
			}
			le++;
		}

		//从右->左，取小于
		while (ri >= left+1) {
			if (a[ri] = 右边索引 ，将ri位置的元素和base 交换
	if (le >= ri) {
		int temp;
		temp = a[left];
		a[left] = a[ri];
		a[ri] = temp;


		quick_sort(a,size,left,ri-1);
		quick_sort(a,size,ri+1,right);
	}
}

// 子组排序算法
int get_key(int a[],int left, int right) {

	//取基准为 a[left]
	int lf1 = left+1;
	int rg1 = right;

	while (true) {	//控制比较躺数
		//左 -> 右  
		while (lf1  a[left]) {
				break;
			}
			lf1++;
		}

		//右 -> 左  
		while (rg1 >= left + 1) {
			if (a[rg1] = rg1) {
		int tmp = a[left];
		a[left] = a[rg1];
		a[rg1] = tmp;
	}

	return rg1;

}

//快速排序——非递归 栈
void quick_sort_no(int a[],int size, int left, int right) {
	if (left>=right) {
		return;
	}

	stack s;
	s.push(left);
	s.push(right);

	while (!s.empty()) {
		int rg = s.top();
		s.pop();
		int lf = s.top();
		s.pop();

		int key = get_key(a,lf, rg);

		cout  lf ) {
			s.push(lf);
			s.push(key-1);
		}
		if (key+1 

// 子组排序算法
int get_key(int a[],int left, int right) {

	//取基准为 a[left]
	int lf1 = left+1;
	int rg1 = right;

	while (true) {	//控制比较躺数
		//左 -> 右  
		while (lf1  a[left]) {
				break;
			}
			lf1++;
		}
		  
		//右 -> 左  
		while (rg1 >= left + 1) {
			if (a[rg1] = rg1) {
		int tmp = a[left];
		a[left] = a[rg1];
		a[rg1] = tmp;
	}

	return rg1;

}

//快速排序——非递归 队列
void quick_sort_no01(int a[], int size, int left, int right) {
	if (left >= right) {
		return;
	}

	queue q;
	q.push(left);
	q.push(right);

	while (!q.empty()) {
		int lf = q.front();
		q.pop();
		int rg = q.front();
		q.pop();

		int key = get_key(a, lf, rg);

		cout  lf) {
			q.push(lf);
			q.push(key - 1);
		}
		if (key + 1 

//基数排序（桶排序）
void radix_sort(int* a,int size) {

	//找出数组中的最大值(顺序查找)
	int max = a[0];
	for (int i = 1; i  max) {
			max = a[i];
		}
	}
	
		//定义一个桶，存放每个位数，出现的元素次数
	int base = 1;
	int* tmp = (int*)malloc(sizeof(int) * size);	//开辟一块连续的地址，作为临时数组
	if (tmp) {
		while (max / base > 0) {
			int data[10] = { 0 };
			//记录元素在每个位数上，出现的次数
			for (int i = 0; i = 0; i--) {
				tmp[data[(a[i] / base) % 10] - 1] = a[i];
				data[(a[i] / base) % 10]--;
			}
			for (int i = 0; i