八大排序算法总结

冒泡排序

  • 比较两两相邻的元素,假如目标是升序序列,那么如果第一个比第二个大,就交换他们两个。
  • 当第一轮交换完毕后,最小的元素就已经归位。
  • 重复以上步骤,比较未归位的元素。

代码如下(c++)

#include<iostream>

using namespace std;

int main(){
	int arr[] = {9, 1, 5, 3, 12, 13, 66, 12, 98};
	for(int i = 0; i < sizeof(arr)/sizeof(int); i++){
		for(int j = i+1; j < sizeof(arr)/sizeof(int); j++){
			if(arr[i] > arr[j]){
				int tmp = arr[i];
				arr[i] = arr[j];
				arr[j] = tmp;
			}
		}
	}
	for(int i = 0; i < sizeof(arr)/sizeof(int); i++){
		cout << arr[i] << " ";
	}
	
	
	return 0;
} 

最好和最坏的时间复杂度都是O(n^2),我们可以从冒泡排序算法中发现,每一次遍历都只归位一个元素。当我们遍历了一遍数组之后如果一次交换都没有进行,就说明所有数字都是正序的,那么我们后续也就不需要再遍历了。这里我们引入一个flag标志,如果某一次遍历结束都没有进行交换,可以直接退出。

优化后最好的时间复杂度是O(n),此时数组本身就是正序。最坏的时间复杂度是O(n^2)。此时数组本身逆序。

优化版冒泡排序代码:

#include<iostream>

using namespace std;

int main(){
	bool flag = false;
	int arr[] = {9, 1, 5, 3, 12, 13, 66, 12, 98};
	for(int i = 0; i < sizeof(arr)/sizeof(int); i++){
		for(int j = i+1; j < sizeof(arr)/sizeof(int); j++){
			if(arr[i] > arr[j]){
				int tmp = arr[i];
				arr[i] = arr[j];
				arr[j] = tmp;
				flag = true;
			}
			if(flag == false){
				break;
			}
		}
		flag = false;
	}
	for(int i = 0; i < sizeof(arr)/sizeof(int); i++){
		cout << arr[i] << " ";
	}
	
	
	return 0;
} 

我们还可以发现在冒泡排序的过程中,对于相同的元素是不会进行交换处理的,所以冒泡排序是稳定的排序算法,且空间复杂度为O(1),不需要消耗额外的空间。

选择排序

  • 从未排序的序列中找出最大(小)的元素,与首个元素交换
  • 从剩下的序列中找出最大(小)的元素,与未排序序列首个元素交换
  • 重复第二个步骤,直到整个序列有序
#include<iostream>

using namespace std;

int main(){
	int arr[] = {9, 1, 5, 3, 12, 13, 66, 12, 98};
	for(int i = 0; i < sizeof(arr)/sizeof(int); i++){
		int mmin = arr[i];
		int pos = i;
		for(int j = i+1; j < sizeof(arr)/sizeof(int); j++){
			if(arr[j] < mmin){
				pos = j;
				mmin = arr[j];
			}
		}
		int tmp = arr[i];
		arr[i] = mmin;
		arr[pos] = tmp;
	}
	for(int i = 0; i < sizeof(arr)/sizeof(int); i++){
		cout << arr[i] << " ";
	}
	
	
	return 0;
}

与冒泡排序类似,但是冒泡排序每次遍历是比较相邻的元素,而选择排序每次遍历是在寻找未排序序列中最大(小)的元素。所以无法像冒泡排序那样进行优化,将最好的情况的时间复杂度优化到O(n)。选择排序的最好,最坏的时间复杂度都是O(n^2)。而且也不是稳定的算法。例如2 1 2 3 6,如果是降序排序,两个2的相对位置会发生变化。

插入排序

  • 将整个序列分为有序和无序两部分
  • 从无序中选择一个元素,然后遍历有序序列中找到适应的位置
  • 将有序序列向后移一位,为选择的元素让位
  • 插入待排序元素
  • 重复以上2、3、4步骤
#include<iostream>

using namespace std;

int main(){
	int arr[] = {9, 1, 5, 3, 12, 13, 66, 12, 98};
	for(int i = 1; i < sizeof(arr)/sizeof(int); i++){
		int tmp = arr[i];
		int j = i-1;
		for(; j >= 0; j--){
			if(arr[j] > tmp){
				arr[j+1] = arr[j];
			}
			else{
				break;
			}
		}
		arr[j+1] = tmp;
	}
	for(int i = 0; i < sizeof(arr)/sizeof(int); i++){
		cout << arr[i] << " ";
	}
	
	
	return 0;
}

相信读者也能发现,每次插入都涉及到已排序序列的整体移动。最坏的情况是整个序列逆序。移动次数为1,2,3,4...n-1。等差数列求和为N^2 / 2。时间复杂度为O(n^2)。最好的情况为整个序列正序,无序交换,时间复杂度为O(n)。相等元素间相对位置不会发生变化,为稳定排序算法。

希尔排序

希尔排序是把序列按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量的逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个序列恰好被分为一组,算法便终止。

实质上就是将待排序数组进行分组,然后分组内进行一次插入排序。一轮结束之后,缩小分组个数,再次进行插入排序,直到整个数组为一组时结束。

具体实现代码如下:

#include<iostream>

using namespace std;

int main(){
	int arr[] = {9, 1, 5, 3, 12, 13, 66, 12, 98};
	int gap;
	int n = sizeof(arr)/sizeof(int);
	for(gap = n >> 1; gap > 0; gap >>= 1){
		for(int i = gap; i < n; i++){
			int tmp = arr[i];
			int j = i - gap;
			for(; j >= 0; j-=gap){
				if(arr[j] > tmp){
					arr[j+gap] = arr[j];
				}
				else{
					break;
				}
			}
			arr[j+gap] = tmp;	
		}
	}
	for(int i = 0; i < sizeof(arr)/sizeof(int); i++){
		cout << arr[i] << " ";
	}
	
	
	return 0;
}

不难发现,在数组基本有序的情况下,直接插入排序较优。但是无序程度越高,希尔排序中所需要移动的次数比起直接插入排序就越少。同时,希尔排序的最坏的情况取决于我们取得增量gap。在排序的过程中gap逐渐紧缩,到最后变成1时就退化为直接插入排序,此时的数组可以看为基本有序,而且也能保证每个元素最终都会被排序到。最坏的时间复杂度是O(nlog^2n)。平均时间复杂度为O(nlogn),且是一个不稳定的排序算法。

桶排序

将各个元素按照自己所属的区间放入相应的桶中,只需要将每个桶的元素排好序,依次输出各个桶内的元素,就得到了有序的元素序列。

我们通常使用一个数组的下标来作为桶号,将每个数值放入对应的桶号当中,最后再将桶中的内容按照桶号输出。

#include<iostream>
#include<memory.h>

using namespace std;

int main(){
	int arr[] = {9, 1, 5, 3, 12, 13, 66, 12, 98};
	int n = sizeof(arr)/sizeof(int);
	int bucket[100];
	memset(bucket,0,sizeof(bucket));
	for(int i = 0; i < n; i++){
		bucket[arr[i]]++;		
	}
	
	for(int i = 0; i < 100; i++){
		while(bucket[i] != 0){
			cout << i << " ";
			bucket[i]--;
		}
	}

	
	return 0;
}

桶排序的时间复杂度只有O(n),但是空间复杂度会随着序列中的元素大小变化而变化。是一种典型的用空间换时间的排序算法。适用于序列各个元素间数值大小变化较小,数据量较为庞大的场景下使用。

快速排序

升序快排实际上就是先找到一个基准数,然后将所有小于基准数的放到他的左边,大于基准数的放到他的右边。每次排序都会将基准数进行归位。这种排序算法很像冒泡排序,但是与之不同的是在归位基准数时,是用两根指针在数组的左右两边同时寻找小于和大于它的数字,如果找到的话会将他们的位置进行交换,如果左右指针重合的话就说明找完了,再将基准数进行归位。然后再对基准数左右两边的子区间继续重复以上过程。通常情况下,我们取最左边的元素为基准数。

实现代码如下

递归快排:

#include<iostream>

using namespace std;

void qsort(int nums[], int left, int right){
	if(left > right) return;
	int num = nums[left];
	int i = left;
	int j = right;
	while(i < j){
		while(i < j && nums[j] >= num) j--;
		while(i < j && nums[i] <= num) i++;
		if(i < j){
			int tmp = nums[i];
			nums[i] = nums[j];
			nums[j] = tmp;
		}
	}
	int tmp = nums[i];
	nums[i] = num;
	nums[left] = tmp;
	qsort(nums,left,i-1);
	qsort(nums,i+1,right);
}

int main(){
	int arr[] = {9, 1, 5, 3, 12, 13, 66, 12, 98};
	qsort(arr,0,sizeof(arr)/sizeof(int)-1);
	for(int i = 0; i < sizeof(arr)/sizeof(int); i++){
		cout << arr[i] << " ";
	}
	
	return 0;
}

非递归快排

#include<iostream>
#include<memory.h>
#include<queue>
using namespace std;

queue<int>q;

void qsort(int nums[],int left,int right){
	q.push(left);
	q.push(right);
	while(!q.empty()){
		int i = q.front();
		left = i;
		q.pop();
		int j = q.front();
		q.pop();
		right = j;
		int num = nums[left];
		while(i < j){
			while(i < j && nums[j] >= num) j--;
			while(i < j && nums[i] <= num) i++;
			if(i < j){
				int tmp = nums[i];
				nums[i] = nums[j];
				nums[j] = tmp;
			}
		}
		nums[left] = nums[i];
		nums[i] = num;
		if(left < i-1){
			q.push(left);
			q.push(i-1);
		}
		if(right > i+1){
			q.push(i+1);
			q.push(right);
		}
	}
}

int main(){
	int arr[] = {9, 1, 5, 3, 12, 13, 66, 12, 98};
	qsort(arr,0,sizeof(arr)/sizeof(int)-1);
	for(int i = 0; i < sizeof(arr)/sizeof(int); i++){
		cout << arr[i] << " ";
	}
	
	return 0;
}

在快排里是左右同时进行查找比较,所以在一般情况下比较的次数是明显少于冒泡排序的。但是在完全逆序的情况下,仍然需要逐个比较后交换,所以最坏的时间复杂度为O(n^2),平均时间复杂度为 O(nlogn)。

归并排序

归并排序采用了分治的思想。

分:将整个待排序序列分为递归分为左右两个部分。

治:将左右两个有序序列进行合并。

以下展示递归实现方法:

#include<iostream>


using std::cout;

int tmp[100] = {0};

void Mergeans(int nums[], int low, int mid, int high){
	for(int i = low; i <= high; i++){
		tmp[i] = nums[i];	
	}
	int i = low;
	int j = mid+1;
	int k = low;
	while(i <= mid && j <= high){
		if(tmp[i] <= tmp[j]){
			nums[k++] = tmp[i++];
		}
		else{
			nums[k++] = tmp[j++];
		}
	}
	while(i <= mid) nums[k++] = tmp[i++];
	while(j <= high) nums[k++] = tmp[j++];
}

void Merge(int nums[],int left, int right){
	if(left >= right) return;
	int mid = (left + right)/2;
	Merge(nums,left,mid);
	Merge(nums,mid+1, right); 
	Mergeans(nums,left,mid,right);
}

int main(){
	int nums[] = {9,8,11,0,5,21,32,6,44,47};
	Merge(nums,0,sizeof(nums)/sizeof(int)-1);
	for(int i = 0; i < sizeof(nums)/sizeof(int); i++){
		cout << nums[i] << " ";
	}
	return 0;
} 

整体思路比较简单,这里就不再赘述。

时间复杂度就是分+治。也就是

f(n) = 2*f(n/2) + n

=2*f(2*f(n/4) + n/2) + n

.....

=2^m*f(n/2^m) + mn

当m足够大时,有:

n/2^m = 1

即m = logn,将其代入得:

f(n) = 2^logn * f(1) + n * logn

因为f(1) = 0

所以 f(n) = nlogn

时间复杂度为O(nlogn)。且是一种稳定的排序算法。

堆排序

堆排序中,我们将一个线性的序列转换成一个完全二叉树的形式。仍然使用线性序列存储。对于完全二叉树,需要利用到以下性质(下标从0开始):

  • 最后一个非叶子节点的下标为2*n-1,n为节点个数。
  • 对于第i个节点,他的左儿子为2*i+1,右儿子为2*i+2。

堆排序算法如下:

  • 维护一个大(小)顶堆
  • 然后将堆顶元素与未排序的最后一个元素交换
  • 整个堆的规模-1,剩下的部分继续重复上述操作。直到堆中只剩一个元素,即完成排序。

如何维护一个大顶堆:

  • 从最后一个非叶子节点开始往前遍历,比较当前节点与其子节点的大小,如果子节点中存在大于当前节点的节点,交换父子节点。

小顶堆同理,此处不再赘述。

整体代码如下:

#include<iostream>

using namespace std;


void createheap(int nums[],int len){
	 int k = len/2 - 1;
	 while(k >= 0){
	 	int j = 2*k+1;
	 	if(j+1 < len){
		 	 if(nums[j] < nums[j+1]){
		 		j = j+1;
		 	 }	
	 	}
	 	if(nums[j] > nums[k]){
	 		int tmp = nums[j];
	 		nums[j] = nums[k];
	 		nums[k] = tmp;
	 	}
	 	k--;
	 }
	 
}

int main(){
	int nums[] = {9,8,11,0,5,21,32,6,44,47};
	int len = sizeof(nums)/sizeof(int);
	while(len!=0){
                createheap(nums,len);
		int tmp = nums[len-1];
		nums[len-1] = nums[0];
		nums[0] = tmp;
		len--;	
	}
	
	for(int i = 0; i < sizeof(nums)/sizeof(int); i++){
		cout << nums[i] << " ";
	}
}

在完全二叉树的基础上进行排序,对于n个节点,需要排序logn+log(n-1)+log(n-2)+...+1。近似的看做O(nlog)。

点赞

发表回复

电子邮件地址不会被公开。必填项已用 * 标注