今天呢,我想给大家分享一下我自己总结的几种排序算法,我们可以一起探讨探讨
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)