[数据结构与算法]数据结构温习篇常见排序算法

前言

之前写了 数据结构排序复习, 但是我觉得之前写的有些地方不够简洁。比如快排。并且这里我实现排序算法不想封装成类了。

排序算法

快速排序

void QuickSort(int* a, int low, int high) {
	int down = low;
	int up = high;
	if (low > high)
		return;
	// 这里以第一个作为主元
	int temp = a[down];
	while(down < up) {
		// 从右边找到第一个比主元小的停下来
		while (down < up && a[up] > temp)
			up--;
		// 从左边找到第一个比主元大的停下来
		while (down < up && a[down] < temp)
			down++;
		// 交换一下
		swap(a[down], a[up]);
	}
	// 把主元放到它应该到的位置上
	a[down] = temp;
	QuickSort(a, low, down - 1);
	QuickSort(a, down + 1, high);
}

完整测试代码:

#include <iostream>
#include <algorithm>
using namespace std;


void QuickSort(int* a, int low, int high) {
	int down = low;
	int up = high;
	if (low > high)
		return;
	// 这里以第一个作为基准 
	int temp = a[down];
	while(down < up) {
		while (down < up && a[up] > temp)
			up--;
		
		while (down < up && a[down] < temp)
			down++;
			
		swap(a[down], a[up]);
	}
	a[down] = temp;
	QuickSort(a, low, down - 1);
	QuickSort(a, down + 1, high);
}

void output(int* a, int n) {
	for (int i = 0; i < n; i++)
		cout << a[i] << " ";
	cout << endl;
}

int main() {
	int n = 6;
	int a[] = {5, 8, 9, 50, 6, 7};
	output(a, n);
	QuickSort(a, 0, n - 1);
	output(a, n);
}