数据结构之排序

一.什么是稳定排序？

排序后相等元素的相对位置不发生变化

二.稳定排序有哪些？

2.1.不稳定排序:快速排序、希尔排序、堆排序

2.2.稳定排序:冒泡排序、插入排序、归并排序、基数排序

三.各大排序算法

3.1.稳定算法

3.1.1.冒泡排序

思想：通过两两比较不断将最大的数浮出水面。一次浮出一个数，需要n-1次。

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100;

void input(int a[],int &n){
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
}

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

void bubbleSort(int a[], int n) {
	for (int i = 0; i < n - 1; i++)
		for (int j = 0; j < n - i - 1; j++)
			if (a[j] > a[j + 1])
				swap(a[j], a[j + 1]);
}

int main() {
	int a[N];
	int n;
	input(a, n);
	bubbleSort(a, n);
	output(a, n);
	return 0;
}

题目：1、已知待排序记录的关键字序列为 {49, 38, 65, 97, 76, 13, 27, 49}，请给出用冒泡排序法进行排序的过程。

第一趟：38 49 65 76 13 27 49 97； 
第二趟：38 49 65 13 27 49 76 97；
第三趟：38 49 13 27 49 65 76 97；
第四趟：38 13 27 49 49 65 76 97；
第五趟：13 27 38 49 49 65 76 97；
第六趟：13 27 38 49 49 65 76 97；
第七趟：13 27 38 49 49 65 76 97

程序运行

3.1.2.插入排序

思想：“扑克牌排序”；由于一个数天然有序，所以从第二个数开始，不断将后续的数插入正确的位置。

#include<iostream>
#include<algorithm>

using namespace std;
const int N = 100;
void input(int a[], int& n) {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
}

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

void insertSort(int a[],int n) {
	for (int i = 1; i < n; i++) {
		int value = a[i];
		int pos = i - 1;
		while (pos >= 0 && a[pos] > value) {
			a[pos + 1] = a[pos];
			pos--;
		}
		a[pos + 1] = value;
	}
}

int main() {
	int n;
	int a[N];
	input(a, n);
	insertSort(a, n);
	output(a, n);
	return 0;
}

3.1.3.归并排序

思想：“分治法的典型之一”；先分再合；保证子块的有序性。

具体的我们以一组无序数列｛14，12，15，13，11，16｝为例分解说明，如下图所示：

#include<iostream>

using namespace std;

const int N = 100;

void input(int a[], int& n) {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
}

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

void merge(int a[], int left, int mid, int right) {
	int l_pos = left, r_pos = mid + 1;
	int pos = left;
	int temp[N];
	while (l_pos <= mid && r_pos <= right) {
		if (a[l_pos] < a[r_pos]) temp[pos++] = a[l_pos++];
		else temp[pos++] = a[r_pos++];
	}
	while (l_pos <= mid) 
		temp[pos++] = a[l_pos++];
	while (r_pos <= right) 
		temp[pos++] = a[r_pos++];
	while (left <= right) {
		a[left] = temp[left];
		left++;
	}
}

void mergeSort(int a[],int left,int right) {
	if (left < right) {
		int mid = (left + right) / 2;
		mergeSort(a, left, mid);
		mergeSort(a, mid + 1, right);
		merge(a, left, mid, right);
	}
}

int main() {
	int a[N];
	int n;
	input(a, n);
	mergeSort(a, 0, n - 1);
	output(a, n);
	return 0;
}

3.2.不稳定算法

3.2.1.堆排序

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 100;

void input(int a[],int& n) {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
}

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

void heapify(int a[],int n,int pos) {
	int l_child = pos * 2 + 1;
	int r_child = pos * 2 + 2;
	int max = pos;
	if (a[max] < a[l_child] && l_child < n) max = l_child;
	if (a[max] < a[r_child] && r_child < n) max = r_child;
	if (max != pos) {
		swap(a[max], a[pos]);
		heapify(a, n, max);
	}
}

void heapSort(int a[], int n) {
	//建堆
	for (int i = n / 2 - 1; i >= 0; i--)
		heapify(a, n, i);
	//排序
	for (int i = n - 1; i > 0; i--) {
		swap(a[0], a[i]);
		heapify(a, i, 0);//维护大顶堆的性质
	}
}

int main() {
	int n;
	int a[N];
	input(a, n);
	heapSort(a, n);
	output(a, n);
	return 0;
}