数据结构 基础排序

数据结构 基础排序

目录

• • 一、冒泡排序
  • 二、选择排序
  • 三、插入排序
  • 四、快速排序
  • 五、归并排序
  • 六、STL sort

---

一、冒泡排序

冒泡排序是一种简单直观的排序算法。这个算法的名字由来是因为越大的元素会经由交换慢慢浮到序列的顶端。

方法：比较相邻的元素。如果第一个比第二个大，就交换他们两个。

void sort(int *a, int l ,int r) {//将数组a从小到大进行排序 ，范围：[l,r] 	
	for(int i = l; i < r; i ++) {
		for(int j = l; j < r - i; j++) {
			if(a[j] > a[j+1]) swap(a[j], a[j+1]);
		}
	} 
}

二、选择排序

在未排序序列中找到最小元素，存放到排序序列的起始位置。

方法：在未排序的序列里选择一个最小值，然后进行交换。

void sort(int *a, int l ,int r) {//将数组a从小到大进行排序 ，范围：[l,r] 	
	for(int i = l ; i < r; i ++) {
		int t = i ;
		for(int j = i + 1; j <= r; j ++) {
			if(a[j] < a[t]) t = j;
		}
		swap( a[i] , a[t] );
	} 
}

三、插入排序

对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

方法：将前 k 个数看做一个有序序列，把第 k + 1 元素当成是未排序的数，插入到前 k 个序列中 。

void sort(int *a, int l ,int r) {//将数组a从小到大进行排序 ，范围：[l,r] 	
	for(int i = l + 1; i <= r; i ++) {
		int t = a[i], j;
		for( j = i; j > l && a[j-1] > t; j --) {
			a[j] = a[j-1];
		}
		a[j] = t;
	} 
}

四、快速排序

基本思想：任取一个元素 为中心，所有比它小的元素一律前放，比它大的元素一律后放，形成左右两个子表；对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。

void msort(int a[], int l, int r) {
	if(l >= r ) return ;
	int i = l - 1, j = r + 1, x = a[l + r >> 1];
	while(i < j) {
		do i ++ ; while(a[i] < x);
		do j -- ; while(a[j] > x);
		if( i < j) swap(a[i], a[j]);
	}
	msort(a, l, j); msort(a, j + 1, r);
}

算法分析：
时间效率：O(nlogn)
空间效率：O(logn）
稳 定 性： 不稳定

注：快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

五、归并排序

基本思想：就是将两个或两个以上的有序表合并为一个有序表的过程。将两个有序表合并为一个有序表的过程称为2路归并，它最为简单和常用。

int a[N],b[N];
void msort(int l,int r) {
	if(l >= r) return ;
	int mid = (l  +r) / 2;
	msort(l, mid); msort(mid + 1, r);
	int i = l , j = mid + 1, t = l;
	while(i <= mid && j <= r) {
		if(a[i] <= a[j]) b[t++] = a[i++];
		else b[t++] = a[j++];
	}
	while(i <= mid) b[t++] = a[i++];
	while(j <= r)   b[t++] = a[j++];
	for(int i = l; i < t; i ++) a[i] = b[i];
}

算法分析：
时间效率：O(nlogn)
空间效率：O(n)
稳 定 性：稳定

六、STL sort

sort 并不是简单的快速排序，它对普通的快速排序进行了优化（结合了插入排序和推排序）。复杂度为O(nlogn) ，是不稳定排序。

1.以数组和 vector 为例

sort(a,a+n);           //将数组[0,n)从小到大排序     
sort(a.begin(),a.end() //将 vector 从小到大排序       

2.重载 sort

方法一：sort(a+l,a+r,cmp)             //将数组[l,r) 根据 cmp 规则进行排序。
方法二：sort(a+l,a+r,greater() ) //将数组[l,r) 从大到小排序
方法三：重载 结构体 或 类 的 < 运算符

注：方法二不能重载结构体。常用方法一，简单实用。

3.其他类似 sort 的函数

void stable_sort(a,a+n)        //可以保留原来顺序，即具有稳定性
void partial_sort(a,a+k,a+n)   //局部排序，前k个有序
type nth_element(a,a+k,a+n)    //返回第k位数