各种排序算法集锦

xiaoxiao2021-02-28  16

今天呢,我想给大家分享一下我自己总结的几种排序算法,我们可以一起探讨探讨

1》直接插入排序

我们先来看一下插入排序的大概过程:

比如现在有一个乱序的数组:{48,62,35,77,55,14,35,98}

<1>tmp  =  62;  {48},blank, 35,77,55,14,35,98}; 

48是否大于tmp,如果大于,48后移到blank

(此时tmp要和-1位置的数字进行比较,但是-1已经越界了,所以直接将tmp赋给-1后面的位置)

如果小于等于tmp,则不做改变;tmp指向下一个待排序数字。

{48,62},35,77,55,14,35,98}

<2>tmp  = 35;    {48,62},blank,77,55,14,35,98};

62>35,将62移至blank,48>35,将48后移至原来62的位置

(此时tmp要和-1位置的数字进行比较,但是-1已经越界了,所以直接将tmp赋给-1后面的位置)

{35,48,62},77,55,14,35,98}

<3>tmp  = 77;    {35,48,62,}blank,55,14,35,98};

62<tmp,77放在62的后面

{35,48,62,77},55,14,35,98}

<4>tmp  = 55;    {35,48,62,77},blank,14,35,98};

77>55,77移至blank的位置,62>55,62移至原来77的位置,48<=55,将55移至48的后面

{35,48,55,62,77}14,35,98}

<5>tmp  = 14;  {35,48,55,62,77,blank,35,98}; 

77>14,77移至blank位置,62>14,62移至原来77的位置,55>14,55移至原来62的位置

48>14,48移至原来55的位置,35>14,将35移至原来48的位置

此时已将是-1位置与tmp进行比较,由于已经走到越界了,将tmp放入-1位置的后面。

{14,35,48,55,62,77},35,98}

<6>tmp  = 35;  {14,35,48,55,62,77},blank,98}; 

77>35,77移至blank的位置,62>35,62移至原来77的位置,55>35,55移至原来62位置

48>35,48移至原来55的位置,35<=35,35移至35的后面。

{14,35,35,48,55,62,77},98}

<7>tmp  = 98;  {14,35,3548,55,62,77},98}; 

77<=98,将98移至77的后面

{14,35,35,48,55,62,77,98}

思路:以第一个数字为基准,tmp保存待排序数字,从待排序数字的前一个数字进行比较,如果大于待排序

数字,则让待排序前一个数字的前一个数字与待排序进行比较,依次类推,直到有一个数字<=待排序数字

将待排序数字插入其后面,一个待排序数字比较完成

tmp保存下一个待排序数字,重复上一个动作。

我们再来看一下代码就很明了了,

void InsertSort(int *arr,int len) { if(NULL == arr || len<=0) { return; } int i; int j; int tmp; for(i = 1;i<len;i++) { tmp = arr[i]; for(j = i-1;j>=0;j--) { if(arr[j]>tmp) arr[j+1]=arr[j]; else break; } arr[j+1] = tmp; } } int main() { int arr[]={48,62,35,77,55,14,35,98}; int len = sizeof(arr)/sizeof(arr[0]); InsertSort(arr,len); for(int i = 0;i<len;i++) { printf("%d ",arr[i]); } }

接下来我i们来分析以下它的稳定性,由于两个相同的数字在移动之前和移动之后的位置没有发生变化,所以

此排序是稳定排序。

稳定性:稳定(越有序越快)

时间复杂度:o(n^2)~o(n):最好的情况下是o(n);都只比较一次

****************************************************************************************************************************

****************************************************************************************************************************

希尔排序:

希尔排序是在是将待排序的关键字序列分成若干个较小的子序列,对子序列进行直接插入排序

在时间耗费上,比直接排序法的性能要好一点。举个例子:

接下来我们看一下代码是怎么实现的呢?????

static void Shell(int *arr,int len,int gap) { if(NULL == arr || len<=0) { return; } int i; int j; int tmp; for(i = gap;i<len;i++) { tmp = arr[i]; for(j = i-gap;j>=0;j-=gap) { if(arr[j]>tmp) arr[j+gap] = arr[j]; else break; } arr[j+gap] = tmp; } } void ShellSort(int *arr,int len) { int gap[] = {4,2,1}; for(int i = 0;i<sizeof(gap)/sizeof(gap[0]);i++) { Shell(arr,len,gap[i]); } } int main() { int arr[] = {46,55,13,42,94,17,5,70}; int len = sizeof(arr)/sizeof(arr[0]); ShellSort(arr,len); for(int i = 0;i<len;i++) { printf("%d ",arr[i]); } return 0; }

稳定性:不稳定,存在跳跃性

时间复杂度:O(n^1.3)~O(n^1.5)

空间复杂度:O(1);

*****************************************************************************************************************

*****************************************************************************************************************

冒泡排序:

冒泡排序算是比较常用的排序了,我们经常会用到:

思路:反复扫描待排序序列,在扫描的过程中顺次比较相邻两个元素的大小,若逆序就交换位置

以升序为例:观察一趟冒泡排序

那么接下来我们来看一下代码是怎么实现的呢??

void BubbleSort(int *arr,int len) { if(NULL == arr || len<=0) { return; } for(int i = 0;i<len-1;i++) { for(int j = 0;j<len-1-i;j++) { if(arr[j]>arr[j+1]) { int tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; } } } } int main() { int arr[] = {48,62,35,77,55,14,35,98,22,40}; int len = sizeof(arr)/sizeof(arr[0]); BubbleSort(arr,len); for(int i = 0;i<len;i++) { printf("%d ",arr[i]); } return 0; }

稳定性:不具有跳跃性,稳定

时间复杂度:o(n^2)

空间复杂度o(1)

***********************************************************************************************************

***********************************************************************************************************

选择排序:

思想:

第一趟简单选择排序时,从第一个待排序数字开始,通过n-1次关键字的比较,从n个记录中选出关键字最小

的记录,并和第一个记录进行交换

第二趟简单选择排序时,从第二个记录开始,通过n-2次关键字比较,从n-1个记录中找到关键字最小的记录,

并和第二个记录进行交换

*******

第i趟简单选择排序时,从第i个记录开始,通过n-i次关键字比较,从n-i+1个记录中找到关键字最小的记录

并和第i个记录进行交换

如此反复,经过n-1趟简单选择排序,将把n-个记录排好序,剩下一个最小记录直接放在最后,所以共需要

n-1趟简单选择排序

举个简单的例子:

看到了这个过程,大家应该对简单选择排序的过程有了一定的了解了,那么再来看一下它的代码实现

void SelectSort(int *arr,int len) { if(NULL == arr || len<=0) { return; } int minindex; for(int i = 0;i<len-1;i++) { minindex = i; for(int j = i+1;j<len;j++) { if(arr[minindex] > arr[j]) minindex = j; } if(minindex != i) { int tmp = arr[i]; arr[i] = arr[minindex]; arr[minindex] = tmp; } } } int main() { int arr[] = {48,62,35,77,55,14,35,98}; int len = sizeof(arr)/sizeof(arr[0]); SelectSort(arr,len); for(int i = 0;i<len;i++) { printf("%d ",arr[i]); } return 0; }

稳定性:

不稳定:举个例子(3,3,2)

时间复杂度:最好,最坏都是o(n^2)

空间复杂度:o(1)

**************************************************************************************************

**************************************************************************************************

快速排序:

思想:从待排序记录中选取一个记录作为基准,通常是第一个,然后将其余比基准小的移动到基准

的前面,大于或等于基准的移动到基准的后面,结果将待排序分成两个子序列,这个过程叫做快排

的一次划分

步骤:假设待排序列为arr[low],arr[low+1],......arr[high]

首先保存基准数字tmp = arr[low],此时arr[low]的位置相当于空位,然后反复进行如下连个扫描过程

直到low和high相遇。

1》high从右向左进行扫描,直到arr[high]<tmp时,将arr[high]移至空单元arr[low],此时arr[high]相当于

空单元

2》low从左向右进行扫描,直到arr[low]>tmp时,将arr[low]移至空单元arr[high],此时arr[low]相当于

空单元

当low和high相遇时,arr[low](或者arr[high])相当于空单元,左边都比它小,右边都比它大,最后将

基准放入其中,完成了快排的一次划分

我们首先来看一个例子,了解一下这个过程:

看了快排的大概过程,那我们再看一下它的代码实现:

#include <iostream> #include <assert.h> using namespace std; static int partition(int *arr,int low,int high) { assert(arr!=NULL); int tmp = arr[low]; while(low<high) { while((low<high)&&arr[high]>=tmp) high--; if(low == high) break; else arr[low] = arr[high]; while((low<high)&&arr[low]<=tmp) low++; if(low == high) break; else arr[high] = arr[low]; } arr[low] = tmp; return low; } static void Quick(int *arr,int low,int high) { if(NULL == arr) return; int par = partition(arr,low,high); if(low<par-1) Quick(arr,low,par-1); if(par<high-1) Quick(arr,par+1,high); } void QuickSort(int *arr,int len) { if(NULL == arr || len<=0) return; Quick(arr,0,len-1); } int main() { int arr[] = {48,62,35,77,55,14,35,98}; int len = sizeof(arr)/sizeof(arr[0]); QuickSort(arr,len); for(int i = 0;i<len;i++) { printf("%d ",arr[i]); } return 0; }

稳定性:存在跳跃性,所以不稳定

时间复杂度:

时间复杂度:                  最好情况:             最坏情况:               空间复杂度:

nlogn                                nlogn                         n^2                           logn

快速排序的优化:

<1>三分取中法(选择基准):优化有序的数据

具体思想:在选取基准时,可以从左中右三个中选取,对它们三个位置上的数据进行排序

取它们中间的那个数据作为基准,并用0下标元素存储基准。

举例:8 1 4 9 6 3 5 2 7 0;

左为8,右为0,中间为6;

在一次分割结束后,可以把与key相等的元素聚在一起,下次分割的时候,不再对相等元素

进行分割。

举例:

待排序列:1  4  6  7  6   6  7  6  8  6

三数取中选取基准:下标为4的6;

一次划分后:对与key相同的元素进行处理:

1  4 6 6 6 6 6 7 8 7

下次划分的两个子序列:1 4和7 8 7;

具体过程:

第一步:在划分的过程中,把与基准值相等的数字放入数组的两端

第二步:划分结束后,把与基准值相同的数字移动到基准值的周围《减少重复》

举例:

待排序列;1 4 6 7 6 6 7 6 8 6

基准值:下标为4的6;

转换后,带分割序列: 6 (基准)    4 6 7 1 6 7 6 8 6

第一步:再划分过程中,把与基准值相等的数字放入数组的两端

结果为:6 4 1         6(基准)       7 8 7 6 6 6

第二步:划分结束后,把与基准值相等的数字移动到基准值周围 

结果:1 4 6    6(基准)   6 6 6 7 8 7

之后:在14和7 8 7两个子序列进行快排。

void swap(int arr[],int first_index,int second_index) { int tmp = arr[first_index]; arr[first_index] = arr[second_index]; arr[second_index] = tmp; } int changeSeondMaxNumber(int *arr,int low,int high) { int mid = low+((high-low)>>1); if(arr[high] <arr[mid]) { swap(arr,mid,high); } if(arr[low] <arr[mid]) { swap(arr,mid,low); } if(arr[low] <arr[high]) { swap(arr,high,low); } /* low的位置保存这三个位置上的中间值 分割时可以直接使用low位置的元素作为基准 而不用改变分割函数了。 */ return arr[low]; } void Qsort(int *arr,int low,int high) { int first = low; int last = high; int left = low; int right = high; int leftlen = 0; int rightlen = 0; if(high-low+1<10) { InsertSort(arr,low,high);//如果数小于10个,就用直接插入法 } //一次分割//使用三数取中法选择基准 int key = changeSeondMaxNumber(arr,low,high); while(low<high) { while(high>low&&arr[high]>=key) { if(arr[high] == key)//处理相等元素 { swap(arr[right],arr[high]); right--; rightlen++; } high--; } arr[low] = arr[high]; while(high>low&&arr[low]<=key) { if(arr[low] == key) { swap(arr[left],arr[low]); left++; leftlen++; } low++; } arr[high] = arr[low]; } arr[low] = key; //一次快排结束 //把与基准key相同的元素移动到最终位置周围 int i = low-1; int j = first; while(j<left&&arr[i]!=key) { swap(arr[i],arr[j]); i--; j++; } i = low+1; j = last; while(j>right&&arr[i]!=key) { swap(arr[i],arr[j]); i++; j--; } Qsort(arr,first,low-1-leftlen); Qsort(arr,low+1+rightlen,last); }

******************************************************************************************************

*****************************************************************************************************

堆排序:

堆排序的过程主要需要解决两个问题:一是按堆定义建初堆,二是去掉最大元之后重建堆,

得到次大元,依次类推

我们以大根堆为例:

问题一:

当堆顶记录改变时,如果重建堆:

首先将与堆相应的完全二叉树根节点中的记录移出,该记录被称为待调整记录,此时根节点相当于空节点

从空节点的左右子树中选出一个关键字较大的记录,如果该记录的关键字大于待调整记录的关键字,则将

该记录上移至空节点当中,此时,原来那个关键字较大的节点相当于空节点,从空节点的左右子树中选取

一个关键字较大的记录,如果该记录的关键字仍大于待调整的关键字,则将该记录上移至空节点。

重复上述移动过程,直到空节点左右子树的关键字均小于待排序记录的关键字,,此时,将待调整记录放入

空节点即可

举例:

             

   

//一次堆调整 void Adijust(int *arr,int start,int end) { int tmp = arr[start]; int parent = start; for(int i = 2*start+1/*父到子*/;i<=end;i=2*i+1/*右孩子*/) { if((i+1<=end)&&(arr[i])<arr[i+1]) i++;//i为左右孩子较大的值的下标 if(tmp<arr[i]) { arr[parent] = arr[i]; parent = i; } else break; } arr[parent] = tmp; }

2:建立大根堆:

思想:将一个任意序列看成完全二叉树,由于叶节点可以视为单元素的堆,因而可以反复利用上述调整

堆算法,自底向上逐层把所有的子树调整为堆,直到将整个完全二叉树调整为堆

可以证明,最后一个非叶节点位于第n/2个位置,

举例:

   

  

//建立大根堆 void HeapSort(int *arr,int len) { if(NULL == arr) return; int i; for(i = (len-1)/2;i>=0;i--) { Adjust(arr,i,len-1); } int tmp; for(i = 0;i<len-1;i++) { tmp = arr[0]; arr[0] = arr[len-1-i]; arr[len-1-i] = tmp; Adjust(arr,0,len-1-i-1); } }

稳定性:不稳定

时间复杂度                        最好                          最坏                    空间

o(nlogn)                             o(nlogn)                     o(nlogn)             o(1)

转载请注明原文地址: https://www.6miu.com/read-1650051.html

最新回复(0)