数据结构--交换排序

数据结构--交换排序

基本思想:

两两比较，如果发生逆序则交换，直到所有记录都排好序为止.

冒泡排序

每趟不断将记录两两比较,并且按照"前小后大"规则交换.

冒泡排序的过程演示

n个记录,需要比较n-1趟.

第m躺需要比较n-m次

冒泡排序算法描述

还可以继续优化:某一趟比较时不出现记录交换,说明已经排好序了

改进的冒泡排序算法

时间复杂度

冒泡排序是稳定的

排序方法的比较

快速排序

改进的交换排序

快速排序动画演示

具体步骤

如何更好的划分子表?

使用low指针和hight指针来动态的划分子表

划分出[1,low-1]和[hight+1,n]两个表

快速排序的算法实现

快速排序的算法分析

快速排序的时间复杂度为O(nlogn)

快速排序的空间复杂度

快速排序不是原地排序

快速排序不稳定

快速排序不是自然排序

快速排序不适于对原本有序或基本有序的记录序列进行排序.

排序方法的比较

快速排序的代码实现

#include <bits/stdc++.h>

using namespace std;
const int N = 100005;
int Partition(int a[], int low, int hight) {
	int piv;
	a[0] = a[low]; //将a[low]赋值给a[0]
	piv = a[low]; //将a[low]的值赋值给piv
	while (low < hight) {
		while (low < hight && a[hight] >= piv) {
			hight--;
		}
		a[low] = a[hight];
		while (low < hight && a[low] <= piv) {
			low++;
		}
		a[hight] = a[low];
	}
	a[low] = a[0]; //将
	return low;//low就是最后piv所在的坐标位置
}
void quick_sort(int a[], int low, int hight) {
	int piv;
	if (low < hight) {
		piv = Partition(a, low, hight);
		quick_sort(a, low, piv - 1);
		quick_sort(a, piv + 1, hight);
	}
}
signed main () {
	int a[N];
	int n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	quick_sort(a, 1, n);
	for (int i = 1; i <= n; i++) {
		cout << a[i] << ' ';
	}
	cout << '\n';
	return 0;
}