排序算法汇总（数据结构）-白红宇

排序算法汇总（数据结构）

阅读量：3898 次

发布时间：2019-05-23

本文共 3831 字，大约阅读时间需要 12 分钟。

1.冒泡排序

排序过程：先选择第一个没有排序的数，与之后的数进行比较，如果这个数比下一个数大的话，那就交换两者位置，如若不是则不动，直到到最后一个数值。

伪代码：

//冒泡排序int  a[20];int n;for(int i=0;i
   
    a[j+1])        swap(a[j],a[j+1]);}

而对于冒泡排序有一个优化的方法，优化在于当一次排序没有进行过交换的时候，也就是之后的顺序都是有序的时候，相当于整个序列都是有序的了。

//冒泡排序优化int  a[20];int n;int falg;//做一个标记位来判断之后需不需要换位for(int i=0;i
   
    a[i+1]){
           //如果进行过交换的话，那就交换，并标记本次循环进行过交换了        swap(a[i],a[i+1]);        falg=1;    }}   //如若没有进行过    if(!falg)        break;    }

算法评价：1.算法的时间复杂度是 0(n^2) 2.该算法是稳定的（因为相对位置一直都没变，就是在比较）

2.快速排序

排序过程：选择一个关键字，通常是序列的第一个或者是最后一个。然后经过一次排序将整个序列分成两部分，左边部分的值都小于选定关键字，右边部分都大于关键字。依次开始对两部分再进行快速排序，直到所有都有序。

伪代码：

void Quick_Sort(ElementType s[],int low,int high){
       if(low < high)//递归跳出条件    {
           int pivotPos = Partition(s,low,high);        Quick_Sort(s,low,pivotPos-1);        Quick_Sort(s,pivotPos+1,high);//对两个子表递归    }}

int Partition(ElementType s[],int low,int high){
       ElementType pivot = s[low];    while(low < high)    {
           while(low < high && s[high] >= pivot) --high;        s[low] = s[high];//将比pivot小的移到左边        while(low < high && s[low] <= pivot) ++low;        s[high] = s[low];//将比pivot大的移到右边    }    a[low] = pivot;    return low;//此时low或者high就是pivot的最终位置}

算法评价：1.平均复杂度是0（nlogn） 2.算法是不稳定的（因为需要将数组进行排序换位分组）

3.直接插入排序

排序过程：相当于就是将s[i]插入到已经排好序的（0–s[i-1]）这个序列当中，具体插入方法是，选中一个大于他，但是前面一个小于他的位置，然后将后面的位置全都向后移一个。

伪代码：

void Insertion_Sort(ElementType s[],int N){
       int i,j;    for(i = 0;i < N;++i)    {
           tmp = s[i];//抽牌        for (j = i; j > 0&&s[j-1] > tmp ; --j)            s[j] = s[j-1];//挪出空位        s[j] = tmp;//落位    }}

算法评价：1.最坏情况是O(n^2) 最好的情况就是原来就是有序的 O(n) 2.算法是稳定的

4.希尔排序

排序过程：将序列以一定值分成一个个部分序列，然后对每个部分序列进行直接插入排序。

伪代码：

void Shell_Sort(ElementType s[],int N){
   	int D,i;	for(D = N / 2;D > 0; D /= 2)//步长变化	{
   		ElementType tmp = s[D];		for (i = D; i >= D && s[i-D] > tmp; i -= D)		{
   			s[i] = s[i-D];		}		s[i] = tmp;	}}

算法评价：1.算法的时间复杂度是评价是：O(n^1.3),最好的情况是O(n) 2.该算法是不稳定的

5.直接选择排序

排序过程：就如名字所说，直接从未排序的序列中选择最小的一个，然后放到已经排好序的序列中，直到序列全部排序好。

伪代码：

void selectSort(ElementType s[],int n){
       int min,i,j;    for (i = 0; i < n - 1; ++i)    {
           min = i;        for ( j = i+1; j < n; ++j)        {
               if(a[j] < s[min])   min = j;        }        if(min != i)    swap(s[i],s[min]);    }}

算法评价：1.算法的时间复杂度是O(n^2) 2.算法是不稳定的（如:(7) 2 5 9 3 4 [7] 1…当我们利用直接选择排序算法进行排序时候,(7)和1调换,(7)就跑到了[7]的后面了,原来的次序改变了,这样就不稳定了.）

6.堆排序

排序过程：首先将序列以一个类似于完全二叉树的形式展现，然后排序成小顶堆或者大顶堆的形式，取出堆顶元素（取出方法：与最后一个节点数据交换，再删去最后节点），将修改后的堆重新排序成大顶堆或者小顶堆，继续进行，直到全部排序完。

伪代码：

/*调整成最大堆*/void HeapAdjust(ElementType s[],int k,int n){
   	ElementType tmp = s[k];	int i;	for(i = s*2; i < n;i *= 2)	{
   		if(i < n && s[i] < s[i+1])//若右孩子大于左孩子，i+1			i++		if(tmp > s[i])//若s[k]已经是最大值，不做操作			break;		s[k] = s[i];		k = i;	}	k[s] = tmp;}void Heap_Sort(ElementType s[],int n){
   	int i;	for (i = n/2; i > 0; --i)		HeapAdjust(s,i,n);	for (int i = n; i > 1; --i)	{
   		swap(s[1],s[i]);		HeapAdjust(s,1,i-1);	}	}

算法评价：1.时间复杂度是：O(nlogn) 2.该算法不是稳定的（因为需要分组，且每组排序情况不一致）

7.归并排序

排序过程：以二路为例：假定待排序列含有n个记录，则可以看作n个有序的子表，每个子表的长度为1，然后两两归并，得到n/2（向上取整）个长度为2或1的子表；再两两归并，…一直重复，直到合并为一个长度为n的有序表为止。

伪代码：

#define MAXSIZE 100void Merge(int *list1,int list1_size,int *list2,int list2_size){
   	int tmp[MAXSIZE];	int i,j,k;	i = j = k = 0;	while(i < list1_size && i < list2_size)//表1，2中都有元素		tmp[k++] = (list1[i] < list2[i]) ? list1[i++] : list2[i++];	while(i < list1_size) tmp[k++] = list1[i++];	while(i < list2_size) tmp[k++] = list2[i++];	for (j = 0; j < (list1_size + list2_size); ++j)		list1[m] = tmp[m];}

void Merge_Sort(int s[],int n){
   	if(n > 1)//递归跳出条件	{
   		int *list1 = s;		int list1_size = n/2;		int *list2 = s + n/2;		int list2_size = n - list1_size;		Merge_Sort(list1,list1_size);		Merge_Sort(list2,list2_size);		Merge(list1,list1_size,list2,list2_size); 	}}

算法评价：1.时间复杂度是O(nlogn) 2.该算法是稳定的（虽然进行了分组，但是组与组之间的相对位置一直都是不变的）

转载地址：http://syfen.baihongyu.com/

你可能感兴趣的文章