内排序小结

浏览数：24 / 时间：2015年06月08日

1.冒泡排序

冒泡排序是一种交换排序，基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止

代码示例：

<span style="font-size:18px;">#include <iostream>
using namespace std;

void BubbleSort(int array[],int length){
	//排序次数比数组长度小1
	bool flag=true; 
	for(int i=0;i<length-1&&flag;i++){ //若flag为false，则退出循环
		flag=false; //初始为fasle
		for(int j=0;j<length-i-1;j++){
			if(array[j]>array[j+1]){
				int temp=array[j];
				array[j]=array[j+1];
				array[j+1]=temp;
				flag=true; //如果发生了数据交换，则flag为true
			}
		}
	}
}
int main(){
	int array[]={12,4,16,15,17,1,19,6};
	BubbleSort(array,8);
	for(int i=0;i<8;i++){
		cout<<array[i]<<" ";
	}
	cout<<endl;
	return 0;
}</span>

时间复杂度分析：最好时间复杂度为O(n),最坏时间复杂度为O(n^2),平均时间复杂度为O(n^2)

空间复杂度分析：O(1)

稳定性分析：稳定的排序算法

2.简单选择排序

基本思想:每一趟排序选择未排序记录关键字的最小值，然后和未排序记录的第一个位置交换数据

示例代码：

<span style="font-size:18px;">#include <iostream>
using namespace std;
void SimpleSelectSort(int array[],int length){
	
	int min;//最小元素下标
	//排序次数比数组长度小1
	for(int i=0;i<length-1;i++){ 
		min=i;//将当前下标定义为最小值下标
		//一趟排序找到当前未排序记录关键字的最小值
		for(int j=i+1;j<length;j++){
			if(array[min]>array[j])
				min=j;
		}
		if(min!=i){ //最小值不是当前i下标值,则交换
			int temp=array[i];
			array[i]=array[min];
			array[min]=temp;
		}
	}
}
int main(){
	int array[]={12,4,16,15,17,5,19,2};
	SimpleSelectSort(array,8);</span><pre name="code" class="cpp"><span style="font-size:18px;"><span style="white-space: pre;">	</span>for(int i=0;i<8;i++){</span>

cout<<array[i]<<" ";}cout<<endl;return 0;}

时间复杂度分析: 由于比较的次数都是O(n^2)次，所以最好、最坏、平均时间复杂度都是O(n^2)

空间复杂度分析:O(1)

稳定性分析：稳定的排序算法

简单选择排序性能上要优于冒泡排序

3.直接插入排序

基本思想：将一个记录插入到一个已经排好序的有序表中，得到一个新的、记录数加1的有序表

示例代码：

#include <iostream>
using namespace std;
void DirectInsertSort(int array[],int length){
	//排序次数比数组长度小1
	for(int i=1;i<length;i++){ 
		if(array[i]<array[i-1]){ //为true才需要真正排序
			int temp=array[i]; //设置哨兵
			int j=i-1;
			//寻找插入位置，当前j值的后一个位置是插入位置
			while(j>=0&&temp<array[j]){ 
				array[j+1]=array[j];
				j--;
			}
			array[j+1]=temp;
		}
	}
}
int main(){
	int array[]={12,4,16,15,17,5,19,2};
	DirectInsertSort(array,8);
	for(int i=0;i<8;i++){
		cout<<array[i]<<" ";
	}
	cout<<endl;
	return 0;
}

时间复杂度分析：最好时间复杂度O(n)、最坏和平均时间复杂度均为O(n^2)

空间复杂度分析：O(1)

稳定性分析：稳定的排序算法

同样的时间复杂度条件下，直接插入排序比冒泡排序和简单选择排序性能要好一些

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

内排序小结