排序_排序算法 - CSDN
排序 订阅
排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序,若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。 [1] 展开全文
排序是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序,若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序。反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。 [1]
信息
排序算法
快速排序、希尔排序、堆排序等
应用学科
数学 计算机
分    类
稳定排序等
中文名
排序
性    质
计算机内经常进行的一种操作
外文名
sequence
排序概念
将杂乱无章的数据元素,通过一定的方法按关键字顺序排列的过程叫做排序。 [2]  快速排序、希尔排序、堆排序、直接选择排序不是稳定的排序算法,而基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。 [1]  ◆稳定排序:假设在待排序的文件中,存在两个或两个以上的记录具有相同的关键字,在用某种排序法排序后,若这些相同关键字的元素的相对次序仍然不变,则这种排序方法是稳定的。其中冒泡,插入,基数,归并属于稳定排序,选择,快速,希尔,归属于不稳定排序。 [3]  ◆就地排序:若排序算法所需的辅助空间并不依赖于问题的规模n,即辅助空间为O(1),则称为就地排序。
收起全文
精华内容
参与话题
  • 八大排序算法

    万次阅读 多人点赞 2020-07-23 12:17:24
    排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说八大排序就是内部排序。 当n较大,则...

    概述

    排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

    我们这里说说八大排序就是内部排序。

        

        当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。

       快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;


     

    1.插入排序—直接插入排序(Straight Insertion Sort)


    基本思想:

    将一个记录插入到已排序好的有序表中,从而得到一个新,记录数增1的有序表。即:先将序列的第1个记录看成是一个有序的子序列,然后从第2个记录逐个进行插入,直至整个序列有序为止。

    要点:设立哨兵,作为临时存储和判断数组边界之用。

    直接插入排序示例:

     

    如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

    算法的实现:

    void print(int a[], int n ,int i){
    	cout<<i <<":";
    	for(int j= 0; j<8; j++){
    		cout<<a[j] <<" ";
    	}
    	cout<<endl;
    }
    
    
    void InsertSort(int a[], int n)
    {
    	for(int i= 1; i<n; i++){
    		if(a[i] < a[i-1]){               //若第i个元素大于i-1元素,直接插入。小于的话,移动有序表后插入
    			int j= i-1;	
    			int x = a[i];		 //复制为哨兵,即存储待排序元素
    			a[i] = a[i-1];           //先后移一个元素
    			while(x < a[j]){	 //查找在有序表的插入位置
    				a[j+1] = a[j];
    				j--;		 //元素后移
    			}
    			a[j+1] = x;		 //插入到正确位置
    		}
    		print(a,n,i);			//打印每趟排序的结果
    	}
    	
    }
    
    int main(){
    	int a[8] = {3,1,5,7,2,4,9,6};
    	InsertSort(a,8);
    	print(a,8,8);
    }
    

     

    效率:

     

    时间复杂度:O(n^2).

    其他的插入排序有二分插入排序,2-路插入排序。

     

     2. 插入排序—希尔排序(Shell`s Sort)


    希尔排序是1959 年由D.L.Shell 提出来的,相对直接排序有较大的改进。希尔排序又叫缩小增量排序

    基本思想:

    先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。

    操作方法:

    1. 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
    2. 按增量序列个数k,对序列进行k 趟排序;
    3. 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

    希尔排序的示例:shell排序的排序过程

    假设待排序文件有10个记录,其关键字分别是:49,38,65,97,76,13,27,49,55,04。

    增量系列的取值依次为:5,3,1

     

    算法实现:

    我们简单处理增量序列:增量序列d = {n/2 ,n/4, n/8 .....1} n为要排序数的个数

    即:先将要排序的一组记录按某个增量d(n/2,n为要排序数的个数)分成若干组子序列,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。继续不断缩小增量直至为1,最后使用直接插入排序完成排序。

    void print(int a[], int n ,int i){
    	cout<<i <<":";
    	for(int j= 0; j<8; j++){
    		cout<<a[j] <<" ";
    	}
    	cout<<endl;
    }
    /**
     * 直接插入排序的一般形式
     *
     * @param int dk 缩小增量,如果是直接插入排序,dk=1
     *
     */
    
    void ShellInsertSort(int a[], int n, int dk)
    {
    	for(int i= dk; i<n; ++i){
    		if(a[i] < a[i-dk]){			//若第i个元素大于i-1元素,直接插入。小于的话,移动有序表后插入
    			int j = i-dk;	
    			int x = a[i];			//复制为哨兵,即存储待排序元素
    			a[i] = a[i-dk];			//首先后移一个元素
    			while(x < a[j]){		//查找在有序表的插入位置
    				a[j+dk] = a[j];
    				j -= dk;			 //元素后移
    			}
    			a[j+dk] = x;			//插入到正确位置
    		}
    		print(a, n,i );
    	}
    	
    }
    
    /**
     * 先按增量d(n/2,n为要排序数的个数进行希尔排序
     *
     */
    void shellSort(int a[], int n){
    
    	int dk = n/2;
    	while( dk >= 1  ){
    		ShellInsertSort(a, n, dk);
    		dk = dk/2;
    	}
    }
    int main(){
    	int a[8] = {3,1,5,7,2,4,9,6};
    	//ShellInsertSort(a,8,1); //直接插入排序
    	shellSort(a,8);			  //希尔插入排序
    	print(a,8,8);
    }
    

     

    希尔排序时效分析很难,关键码的比较次数与记录移动次数依赖于增量因子序列d的选取,特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法,有取奇数的,也有取质数的,但需要注意:增量因子中除1 外没有公因子,且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。

     

    3. 选择排序—简单选择排序(Simple Selection Sort)


    基本思想:

    在要排序的一组数中,选出最小(或者最大)的一个数与第1个位置的数交换;然后在剩下的数当中再找最小(或者最大)的与第2个位置的数交换,依次类推,直到第n-1个元素(倒数第二个数)和第n个元素(最后一个数)比较为止。

    简单选择排序的示例:

     

    操作方法:

    第一趟,从n 个记录中找出关键码最小的记录与第一个记录交换;

    第二趟,从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换;

    以此类推.....

    第i 趟,则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换,

    直到整个序列按关键码有序。

     

    算法实现:

    void print(int a[], int n ,int i){
    	cout<<"第"<<i+1 <<"趟 : ";
    	for(int j= 0; j<8; j++){
    		cout<<a[j] <<"  ";
    	}
    	cout<<endl;
    }
    /**
     * 数组的最小值
     *
     * @return int 数组的键值
     */
    int SelectMinKey(int a[], int n, int i)
    {
    	int k = i;
    	for(int j=i+1 ;j< n; ++j) {
    		if(a[k] > a[j]) k = j;
    	}
    	return k;
    }
    
    /**
     * 选择排序
     *
     */
    void selectSort(int a[], int n){
    	int key, tmp;
    	for(int i = 0; i< n; ++i) {
    		key = SelectMinKey(a, n,i);           //选择最小的元素
    		if(key != i){
    			tmp = a[i];  a[i] = a[key]; a[key] = tmp; //最小元素与第i位置元素互换
    		}
    		print(a,  n , i);
    	}
    }
    int main(){
    	int a[8] = {3,1,5,7,2,4,9,6};
    	cout<<"初始值:";
    	for(int j= 0; j<8; j++){
    		cout<<a[j] <<"  ";
    	}
    	cout<<endl<<endl;
    	selectSort(a, 8);
    	print(a,8,8);
    }
    

     

     简单选择排序的改进——二元选择排序

     

    简单选择排序,每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素(当前趟最大和最小记录)的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序,最多只需进行[n/2]趟循环即可。具体实现如下:

    /** 这是伪函数, 逻辑判断不严谨
    void selectSort(int r[],int n) {
    	int i ,j , min ,max, tmp;
    	for (i=1 ;i <= n/2;i++) {  
    		// 做不超过n/2趟选择排序 
    		min = i; max = i ; //分别记录最大和最小关键字记录位置
    		for (j= i+1; j<= n-i; j++) {
    			if (r[j] > r[max]) { 
    				max = j ; continue ; 
    			}  
    			if (r[j]< r[min]) { 
    				min = j ; 
    			}   
    	  }  
    	  //该交换操作还可分情况讨论以提高效率
    	  tmp = r[i-1]; r[i-1] = r[min]; r[min] = tmp;
    	  tmp = r[n-i]; r[n-i] = r[max]; r[max] = tmp; 
     
    	} 
    }
     */
    void selectSort(int a[],int len) {
            int i,j,min,max,tmp;  
            for(i=0; i<len/2; i++){  // 做不超过n/2趟选择排序 
                min = max = i;  
                for(j=i+1; j<=len-1-i; j++){  
    				//分别记录最大和最小关键字记录位置
                    if(a[j] > a[max]){  
                        max = j;  
                        continue;  
                    }  
                    if(a[j] < a[min]){  
                        min = j;  
                    }  
                }  
    			//该交换操作还可分情况讨论以提高效率
                if(min != i){//当第一个为min值,不用交换  
                    tmp=a[min];  a[min]=a[i];  a[i]=tmp;  
                }  
                if(min == len-1-i && max == i)//当第一个为max值,同时最后一个为min值,不再需要下面操作  
                    continue;  
                if(max == i)//当第一个为max值,则交换后min的位置为max值  
                    max = min;  
                if(max != len-1-i){//当最后一个为max值,不用交换  
                    tmp=a[max];  a[max]=a[len-1-i];  a[len-1-i]=tmp;  
                }
    			print(a,len, i);			
            }  
     }

     

    4. 选择排序—堆排序(Heap Sort)


    堆排序是一种树形选择排序,是对直接选择排序的有效改进。

    基本思想:

    堆的定义如下:具有n个元素的序列(k1,k2,...,kn),当且仅当满足

    时称之为堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)。
    若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的。如:

    (a)大顶堆序列:(96, 83,27,38,11,09)

      (b)  小顶堆序列:(12,36,24,85,47,30,53,91)

    初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树(一维数组存储二叉树),调整它们的存储序,使之成为一个堆,将堆顶元素输出,得到n 个元素中最小(或最大)的元素,这时堆的根节点的数最小(或者最大)。然后对前面(n-1)个元素重新调整使之成为堆,输出堆顶元素,得到n 个元素中次小(或次大)的元素。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。称这个过程为堆排序

    因此,实现堆排序需解决两个问题:
    1. 如何将n 个待排序的数建成堆;
    2. 输出堆顶元素后,怎样调整剩余n-1 个元素,使其成为一个新堆。


    首先讨论第二个问题:输出堆顶元素后,对剩余n-1元素重新建成堆的调整过程。
    调整小顶堆的方法:

    1)设有m 个元素的堆,输出堆顶元素后,剩下m-1 个元素。将堆底元素送入堆顶((最后一个元素与堆顶进行交换),堆被破坏,其原因仅是根结点不满足堆的性质。

    2)将根结点与左、右子树中较小元素的进行交换。

    3)若与左子树交换:如果左子树堆被破坏,即左子树的根结点不满足堆的性质,则重复方法 (2).

    4)若与右子树交换,如果右子树堆被破坏,即右子树的根结点不满足堆的性质。则重复方法 (2).

    5)继续对不满足堆性质的子树进行上述交换操作,直到叶子结点,堆被建成。

    称这个自根结点到叶子结点的调整过程为筛选。如图:


    再讨论对n 个元素初始建堆的过程。
    建堆方法:对初始序列建堆的过程,就是一个反复进行筛选的过程。

    1)n 个结点的完全二叉树,则最后一个结点是第个结点的子树。

    2)筛选从第个结点为根的子树开始,该子树成为堆。

    3)之后向前依次对各结点为根的子树进行筛选,使之成为堆,直到根结点。

    如图建堆初始过程:无序序列:(49,38,65,97,76,13,27,49)


                                 

     算法的实现:

    从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。

    void print(int a[], int n){
    	for(int j= 0; j<n; j++){
    		cout<<a[j] <<"  ";
    	}
    	cout<<endl;
    }
    
    
    
    /**
     * 已知H[s…m]除了H[s] 外均满足堆的定义
     * 调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选, 
     *
     * @param H是待调整的堆数组
     * @param s是待调整的数组元素的位置
     * @param length是数组的长度
     *
     */
    void HeapAdjust(int H[],int s, int length)
    {
    	int tmp  = H[s];
    	int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)
        while (child < length) {
    		if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)
    			++child ;
    		}
    		if(H[s]<H[child]) {  // 如果较大的子结点大于父结点
    			H[s] = H[child]; // 那么把较大的子结点往上移动,替换它的父结点
    			s = child;		 // 重新设置s ,即待调整的下一个结点的位置
    			child = 2*s+1;
    		}  else {			 // 如果当前待调整结点大于它的左右孩子,则不需要调整,直接退出
    			 break;
    		}
    		H[s] = tmp;			// 当前待调整的结点放到比其大的孩子结点位置上
    	}
    	print(H,length);
    }
    
    
    /**
     * 初始堆进行调整
     * 将H[0..length-1]建成堆
     * 调整完之后第一个元素是序列的最小的元素
     */
    void BuildingHeap(int H[], int length)
    { 
    	//最后一个有孩子的节点的位置 i=  (length -1) / 2
    	for (int i = (length -1) / 2 ; i >= 0; --i)
    		HeapAdjust(H,i,length);
    }
    /**
     * 堆排序算法
     */
    void HeapSort(int H[],int length)
    {
        //初始堆
    	BuildingHeap(H, length);
    	//从最后一个元素开始对序列进行调整
    	for (int i = length - 1; i > 0; --i)
    	{
    		//交换堆顶元素H[0]和堆中最后一个元素
    		int temp = H[i]; H[i] = H[0]; H[0] = temp;
    		//每次交换堆顶元素和堆中最后一个元素之后,都要对堆进行调整
    		HeapAdjust(H,0,i);
      }
    } 
    
    int main(){
    	int H[10] = {3,1,5,7,2,4,9,6,10,8};
    	cout<<"初始值:";
    	print(H,10);
    	HeapSort(H,10);
    	//selectSort(a, 8);
    	cout<<"结果:";
    	print(H,10);
    
    }
    
    

     

    分析:

    设树深度为k,。从根到叶的筛选,元素比较次数至多2(k-1)次,交换记录至多k 次。所以,在建好堆后,排序过程中的筛选次数不超过下式: 

                                   

    而建堆时的比较次数不超过4n 次,因此堆排序最坏情况下,时间复杂度也为:O(nlogn )。

     

    5. 交换排序—冒泡排序(Bubble Sort)


    基本思想:

    在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

    冒泡排序的示例:

     

    算法的实现:

    void bubbleSort(int a[], int n){
    	for(int i =0 ; i< n-1; ++i) {
    		for(int j = 0; j < n-i-1; ++j) {
    			if(a[j] > a[j+1])
    			{
    				int tmp = a[j] ; a[j] = a[j+1] ;  a[j+1] = tmp;
    			}
    		}
    	}
    }

     

    冒泡排序算法的改进

    对冒泡排序常见的改进方法是加入一标志性变量exchange,用于标志某一趟排序过程中是否有数据交换,如果进行某一趟排序时并没有进行数据交换,则说明数据已经按要求排列好,可立即结束排序,避免不必要的比较过程。本文再提供以下两种改进算法:

    1.设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。

    改进后算法如下:

    void Bubble_1 ( int r[], int n) {
    	int i= n -1;  //初始时,最后位置保持不变
    	while ( i> 0) { 
    		int pos= 0; //每趟开始时,无记录交换
    		for (int j= 0; j< i; j++)
    			if (r[j]> r[j+1]) {
    				pos= j; //记录交换的位置 
    				int tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
    			} 
    		i= pos; //为下一趟排序作准备
    	 } 
    }  
    

     

    2.传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

    改进后的算法实现为:

    void Bubble_2 ( int r[], int n){
    	int low = 0; 
    	int high= n -1; //设置变量的初始值
    	int tmp,j;
    	while (low < high) {
    		for (j= low; j< high; ++j) //正向冒泡,找到最大者
    			if (r[j]> r[j+1]) {
    				tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;
    			} 
    		--high;					//修改high值, 前移一位
    		for ( j=high; j>low; --j) //反向冒泡,找到最小者
    			if (r[j]<r[j-1]) {
    				tmp = r[j]; r[j]=r[j-1];r[j-1]=tmp;
    			}
    		++low;					//修改low值,后移一位
    	} 
    } 

     

    6. 交换排序—快速排序(Quick Sort)


    基本思想:

    1)选择一个基准元素,通常选择第一个元素或者最后一个元素,

    2)通过一趟排序讲待排序的记录分割成独立的两部分,其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。

    3)此时基准元素在其排好序后的正确位置

    4)然后分别对这两部分记录用同样的方法继续进行排序,直到整个序列有序。

    快速排序的示例:

    (a)一趟排序的过程:

    (b)排序的全过程

    算法的实现:

     递归实现:

    void print(int a[], int n){
    	for(int j= 0; j<n; j++){
    		cout<<a[j] <<"  ";
    	}
    	cout<<endl;
    }
    
    void swap(int *a, int *b)
    {
    	int tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    
    int partition(int a[], int low, int high)
    {
    	int privotKey = a[low];								//基准元素
    	while(low < high){								    //从表的两端交替地向中间扫描
    		while(low < high  && a[high] >= privotKey) --high;  //从high 所指位置向前搜索,至多到low+1 位置。将比基准元素小的交换到低端
    		swap(&a[low], &a[high]);
    		while(low < high  && a[low] <= privotKey ) ++low;
    		swap(&a[low], &a[high]);
    	}
    	print(a,10);
    	return low;
    }
    
    
    void quickSort(int a[], int low, int high){
    	if(low < high){
    		int privotLoc = partition(a,  low,  high);  //将表一分为二
    		quickSort(a,  low,  privotLoc -1);			//递归对低子表递归排序
    		quickSort(a,   privotLoc + 1, high);		//递归对高子表递归排序
    	}
    }
    
    int main(){
    	int a[10] = {3,1,5,7,2,4,9,6,10,8};
    	cout<<"初始值:";
    	print(a,10);
    	quickSort(a,0,9);
    	cout<<"结果:";
    	print(a,10);
    
    }

     

    分析:

    快速排序是通常被认为在同数量级(O(nlog2n))的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时,快排序反而蜕化为冒泡排序。为改进之,通常以“三者取中法”来选取基准记录,即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。


    快速排序的改进

    在本改进算法中,只对长度大于k的子序列递归调用快速排序,让原序列基本有序,然后再对整个基本有序序列用插入排序算法排序。实践证明,改进后的算法时间复杂度有所降低,且当k取值为 8 左右时,改进算法的性能最佳。算法思想如下:

    void print(int a[], int n){
    	for(int j= 0; j<n; j++){
    		cout<<a[j] <<"  ";
    	}
    	cout<<endl;
    }
    
    void swap(int *a, int *b)
    {
    	int tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    
    int partition(int a[], int low, int high)
    {
    	int privotKey = a[low];					//基准元素
    	while(low < high){					//从表的两端交替地向中间扫描
    		while(low < high  && a[high] >= privotKey) --high; //从high 所指位置向前搜索,至多到low+1 位置。将比基准元素小的交换到低端
    		swap(&a[low], &a[high]);
    		while(low < high  && a[low] <= privotKey ) ++low;
    		swap(&a[low], &a[high]);
    	}
    	print(a,10);
    	return low;
    }
    
    
    void qsort_improve(int r[ ],int low,int high, int k){
    	if( high -low > k ) { //长度大于k时递归, k为指定的数
    		int pivot = partition(r, low, high); // 调用的Partition算法保持不变
    		qsort_improve(r, low, pivot - 1,k);
    		qsort_improve(r, pivot + 1, high,k);
    	} 
    } 
    void quickSort(int r[], int n, int k){
    	qsort_improve(r,0,n,k);//先调用改进算法Qsort使之基本有序
    
    	//再用插入排序对基本有序序列排序
    	for(int i=1; i<=n;i ++){
    		int tmp = r[i]; 
    		int j=i-1;
    		while(tmp < r[j]){
    			r[j+1]=r[j]; j=j-1; 
    		}
    		r[j+1] = tmp;
    	} 
    
    } 
    
    
    
    int main(){
    	int a[10] = {3,1,5,7,2,4,9,6,10,8};
    	cout<<"初始值:";
    	print(a,10);
    	quickSort(a,9,4);
    	cout<<"结果:";
    	print(a,10);
    
    }

     

    7. 归并排序(Merge Sort)


    基本思想:

    归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

    归并排序示例:

     

     

    合并方法:

    设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成,两个子表长度分别为n-i +1、n-m。

    1. j=m+1;k=i;i=i; //置两个子表的起始下标及辅助数组的起始下标
    2. 若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束
    3. //选取r[i]和r[j]较小的存入辅助数组rf
      如果r[i]<r[j],rf[k]=r[i]; i++; k++; 转⑵
      否则,rf[k]=r[j]; j++; k++; 转⑵
    4. //将尚未处理完的子表中元素存入rf
      如果i<=m,将r[i…m]存入rf[k…n] //前一子表非空
      如果j<=n ,  将r[j…n] 存入rf[k…n] //后一子表非空
    5. 合并结束。
    //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]
    void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
    {
    	int j,k;
    	for(j=m+1,k=i; i<=m && j <=n ; ++k){
    		if(r[j] < r[i]) rf[k] = r[j++];
    		else rf[k] = r[i++];
    	}
    	while(i <= m)  rf[k++] = r[i++];
    	while(j <= n)  rf[k++] = r[j++];
    }

     

    归并的迭代算法

    1 个元素的表总是有序的。所以对n 个元素的待排序列,每个元素可看成1 个有序子表。对子表两两合并生成n/2个子表,所得子表除最后一个子表长度可能为1 外,其余子表长度均为2。再进行两两合并,直到生成n 个元素按关键码有序的表。

    void print(int a[], int n){
    	for(int j= 0; j<n; j++){
    		cout<<a[j] <<"  ";
    	}
    	cout<<endl;
    }
    
    //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]
    void Merge(ElemType *r,ElemType *rf, int i, int m, int n)
    {
    	int j,k;
    	for(j=m+1,k=i; i<=m && j <=n ; ++k){
    		if(r[j] < r[i]) rf[k] = r[j++];
    		else rf[k] = r[i++];
    	}
    	while(i <= m)  rf[k++] = r[i++];
    	while(j <= n)  rf[k++] = r[j++];
    	print(rf,n+1);
    }
    
    void MergeSort(ElemType *r, ElemType *rf, int lenght)
    { 
    	int len = 1;
    	ElemType *q = r ;
    	ElemType *tmp ;
    	while(len < lenght) {
    		int s = len;
    		len = 2 * s ;
    		int i = 0;
    		while(i+ len <lenght){
    			Merge(q, rf,  i, i+ s-1, i+ len-1 ); //对等长的两个子表合并
    			i = i+ len;
    		}
    		if(i + s < lenght){
    			Merge(q, rf,  i, i+ s -1, lenght -1); //对不等长的两个子表合并
    		}
    		tmp = q; q = rf; rf = tmp; //交换q,rf,以保证下一趟归并时,仍从q 归并到rf
    	}
    }
    
    
    int main(){
    	int a[10] = {3,1,5,7,2,4,9,6,10,8};
    	int b[10];
    	MergeSort(a, b, 10);
    	print(b,10);
    	cout<<"结果:";
    	print(a,10);
    
    }

     

    两路归并的递归算法

    void MSort(ElemType *r, ElemType *rf,int s, int t)
    { 
    	ElemType *rf2;
    	if(s==t) r[s] = rf[s];
    	else
    	{ 
    		int m=(s+t)/2;			/*平分*p 表*/
    		MSort(r, rf2, s, m);		/*递归地将p[s…m]归并为有序的p2[s…m]*/
    		MSort(r, rf2, m+1, t);		/*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/
    		Merge(rf2, rf, s, m+1,t);	/*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/
    	}
    }
    void MergeSort_recursive(ElemType *r, ElemType *rf, int n)
    {   /*对顺序表*p 作归并排序*/
    	MSort(r, rf,0, n-1);
    }

    8. 桶排序/基数排序(Radix Sort)

    说基数排序之前,我们先说桶排序:

    基本思想:是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。
             简单来说,就是把数据分组,放在一个个的桶中,然后对每个桶里面的在进行排序。  

     

     例如要对大小为[1..1000]范围内的n个整数A[1..n]排序  

     首先,可以把桶设为大小为10的范围,具体而言,设集合B[1]存储[1..10]的整数,集合B[2]存储   (10..20]的整数,……集合B[i]存储(   (i-1)*10,   i*10]的整数,i   =   1,2,..100。总共有  100个桶。  

      然后,对A[1..n]从头到尾扫描一遍,把每个A[i]放入对应的桶B[j]中。  再对这100个桶中每个桶里的数字排序,这时可用冒泡,选择,乃至快排,一般来说任  何排序法都可以。

      最后,依次输出每个桶里面的数字,且每个桶中的数字从小到大输出,这  样就得到所有数字排好序的一个序列了。  

      假设有n个数字,有m个桶,如果数字是平均分布的,则每个桶里面平均有n/m个数字。如果  

      对每个桶中的数字采用快速排序,那么整个算法的复杂度是  

      O(n   +   m   *   n/m*log(n/m))   =   O(n   +   nlogn   -   nlogm)  

      从上式看出,当m接近n的时候,桶排序复杂度接近O(n)  

      当然,以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的  ,实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中,那就退化成一般的排序了。  

            前面说的几大排序算法 ,大部分时间复杂度都是O(n2),也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O(n)的时间复杂度。但桶排序的缺点是:

            1)首先是空间复杂度比较高,需要的额外开销大。排序有两个数组的空间开销,一个存放待排序数组,一个就是所谓的桶,比如待排序值是从0到m-1,那就需要m个桶,这个桶数组就要至少m个空间。

            2)其次待排序的元素都要在一定的范围内等等。

           桶式排序是一种分配排序。分配排序的特定是不需要进行关键码的比较,但前提是要知道待排序列的一些具体情况。

     

    分配排序的基本思想:说白了就是进行多次的桶式排序。

    基数排序过程无须比较关键字,而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶:O(n)。

    实例:

    扑克牌中52 张牌,可按花色和面值分成两个字段,其大小关系为:
    花色: 梅花< 方块< 红心< 黑心  
    面值: 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A

    若对扑克牌按花色、面值进行升序排序,得到如下序列:


    即两张牌,若花色不同,不论面值怎样,花色低的那张牌小于花色高的,只有在同花色情况下,大小关系才由面值的大小确定。这就是多关键码排序。

    为得到排序结果,我们讨论两种排序方法。
    方法1:先对花色排序,将其分为4 个组,即梅花组、方块组、红心组、黑心组。再对每个组分别按面值进行排序,最后,将4 个组连接起来即可。
    方法2:先按13 个面值给出13 个编号组(2 号,3 号,...,A 号),将牌按面值依次放入对应的编号组,分成13 堆。再按花色给出4 个编号组(梅花、方块、红心、黑心),将2号组中牌取出分别放入对应花色组,再将3 号组中牌取出分别放入对应花色组,……,这样,4 个花色组中均按面值有序,然后,将4 个花色组依次连接起来即可。

    设n 个元素的待排序列包含d 个关键码{k1,k2,…,kd},则称序列对关键码{k1,k2,…,kd}有序是指:对于序列中任两个记录r[i]和r[j](1≤i≤j≤n)都满足下列有序关系:

                                                                  

    其中k1 称为最主位关键码,kd 称为最次位关键码     。

     

    两种多关键码排序方法:

    多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序,分两种方法:

    最高位优先(Most Significant Digit first)法,简称MSD 法

    1)先按k1 排序分组,将序列分成若干子序列,同一组序列的记录中,关键码k1 相等。

    2)再对各组按k2 排序分成子组,之后,对后面的关键码继续这样的排序分组,直到按最次位关键码kd 对各子组排序后。

    3)再将各组连接起来,便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是MSD 法。

    最低位优先(Least Significant Digit first)法,简称LSD 法

    1) 先从kd 开始排序,再对kd-1进行排序,依次重复,直到按k1排序分组分成最小的子序列后。

    2) 最后将各个子序列连接起来,便可得到一个有序的序列, 扑克牌按花色、面值排序中介绍的方法二即是LSD 法。

     

    基于LSD方法的链式基数排序的基本思想

      “多关键字排序”的思想实现“单关键字排序”。对数字型或字符型的单关键字,可以看作由多个数位或多个字符构成的多关键字,此时可以采用“分配-收集”的方法进行排序,这一过程称作基数排序法,其中每个数字或字符可能的取值个数称为基数。比如,扑克牌的花色基数为4,面值基数为13。在整理扑克牌时,既可以先按花色整理,也可以先按面值整理。按花色整理时,先按红、黑、方、花的顺序分成4摞(分配),再按此顺序再叠放在一起(收集),然后按面值的顺序分成13摞(分配),再按此顺序叠放在一起(收集),如此进行二次分配和收集即可将扑克牌排列有序。   

    基数排序:

    是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以是稳定的。

    算法实现:

    Void RadixSort(Node L[],length,maxradix)
    {
       int m,n,k,lsp;
       k=1;m=1;
       int temp[10][length-1];
       Empty(temp); //清空临时空间
       while(k<maxradix) //遍历所有关键字
       {
         for(int i=0;i<length;i++) //分配过程
        {
           if(L[i]<m)
              Temp[0][n]=L[i];
           else
              Lsp=(L[i]/m)%10; //确定关键字
           Temp[lsp][n]=L[i];
           n++;
       }
       CollectElement(L,Temp); //收集
       n=0;
       m=m*10;
      k++;
     }
    }

     

     

     

    总结


    各种排序的稳定性,时间复杂度和空间复杂度总结:

     我们比较时间复杂度函数的情况:

     

                                 时间复杂度函数O(n)的增长情况

    所以对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法。

     

    时间复杂度来说:

    (1)平方阶(O(n2))排序
      各类简单排序:直接插入、直接选择和冒泡排序;
     (2)线性对数阶(O(nlog2n))排序
      快速排序、堆排序和归并排序;
     (3)O(n1+§))排序,§是介于0和1之间的常数。

           希尔排序
    (4)线性阶(O(n))排序
      基数排序,此外还有桶、箱排序。

    说明:

    当原表有序或基本有序时,直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数,时间复杂度可降至O(n);

    而快速排序则相反,当原表基本有序时,将蜕化为冒泡排序,时间复杂度提高为O(n2);

    原表是否有序,对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

     

    稳定性:

    排序算法的稳定性:若待排序的序列中,存在多个具有相同关键字的记录,经过排序, 这些记录的相对次序保持不变,则称该算法是稳定的;若经排序后,记录的相对 次序发生了改变,则称该算法是不稳定的。 
         稳定性的好处:排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。另外,如果排序算法稳定,可以避免多余的比较;

    稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序

    不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序

     

    选择排序算法准则:

    每种排序算法都各有优缺点。因此,在实用时需根据不同情况适当选用,甚至可以将多种方法结合起来使用。

    选择排序算法的依据

    影响排序的因素有很多,平均时间复杂度低的算法并不一定就是最优的。相反,有时平均时间复杂度高的算法可能更适合某些特殊情况。同时,选择算法时还得考虑它的可读性,以利于软件的维护。一般而言,需要考虑的因素有以下四点:

    1.待排序的记录数目n的大小;

    2.记录本身数据量的大小,也就是记录中除关键字外的其他信息量的大小;

    3.关键字的结构及其分布情况;

    4.对排序稳定性的要求。

    设待排序元素的个数为n.

    1)当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。

       快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;
           堆排序 :  如果内存空间允许且要求稳定性的,

           归并排序:它有一定数量的数据移动,所以我们可能过与插入排序组合,先获得一定长度的序列,然后再合并,在效率上将有所提高。

    2)  当n较大,内存空间允许,且要求稳定性 =》归并排序

    3)当n较小,可采用直接插入或直接选择排序。

        直接插入排序:当元素分布有序,直接插入排序将大大减少比较次数和移动记录的次数。

        直接选择排序 :元素分布有序,如果不要求稳定性,选择直接选择排序

    5)一般不使用或不直接使用传统的冒泡排序。

    6)基数排序
    它是一种稳定的排序算法,但有一定的局限性:
      1、关键字可分解。
      2、记录的关键字位数较少,如果密集更好
      3、如果是数字时,最好是无符号的,否则将增加相应的映射复杂度,可先将其正负分开排序。

     

    注明:转载请提示出处:http://blog.csdn.net/hguisu/article/details/7776068

     

     

     

    感谢您的支持,我会继续努力的! 扫码打赏,你说多少就多少

             

    展开全文
  • 常见的7种排序算法

    万次阅读 多人点赞 2019-04-27 17:04:36
    1、冒泡排序 最简单的一种排序算法。假设长度为n的数组arr,要按照从小到大排序。则冒泡排序的具体过程可以描述为:首先从数组的第一个元素开始到数组最后一个元素为止,对数组中相邻的两个元素进行比较,如果位于...

    1、冒泡排序

    最简单的一种排序算法。假设长度为n的数组arr,要按照从小到大排序。则冒泡排序的具体过程可以描述为:首先从数组的第一个元素开始到数组最后一个元素为止,对数组中相邻的两个元素进行比较,如果位于数组左端的元素大于数组右端的元素,则交换这两个元素在数组中的位置,此时数组最右端的元素即为该数组中所有元素的最大值。接着对该数组剩下的n-1个元素进行冒泡排序,直到整个数组有序排列。算法的时间复杂度为O(n^2)。

    // 冒泡排序
    void BubbleSort(int arr[], int length)
    {
    	for (int i = 0; i < length; i++)
    	{
    		for (int j = 0; j < length -  i - 1; j++)
    		{
    			if (arr[j] > arr[j + 1])
    			{
    				int temp;
    				temp = arr[j + 1];
    				arr[j + 1] = arr[j];
    				arr[j] = temp;
    			}
    		}
    	}
    }

    2、选择排序

    严蔚敏版《数据结构》中对选择排序的基本思想描述为:每一趟在n-i+1(i=1,2,...,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。具体来说,假设长度为n的数组arr,要按照从小到大排序,那么先从n个数字中找到最小值min1,如果最小值min1的位置不在数组的最左端(也就是min1不等于arr[0]),则将最小值min1和arr[0]交换,接着在剩下的n-1个数字中找到最小值min2,如果最小值min2不等于arr[1],则交换这两个数字,依次类推,直到数组arr有序排列。算法的时间复杂度为O(n^2)。

    // 选择排序
    void SelectionSort(int arr[], int length)
    {
    	for (int i = 0; i < length; i++)
    	{
    		int index = i;
    		for (int j = i+1; j < length; j++)
    		{
    			if (arr[j] < arr[index])
    			{
    				index = j;
    			}
    		}
    		if (index == i)
    			continue;
    		else
    		{
    			int temp;
    			temp = arr[index];
    			arr[index] = arr[i];
    			arr[i] = temp;
    		}
    	}
    }

    3、插入排序

     插入排序的基本思想就是将无序序列插入到有序序列中。例如要将数组arr=[4,2,8,0,5,1]排序,可以将4看做是一个有序序列(图中用蓝色标出),将[2,8,0,5,1]看做一个无序序列。无序序列中2比4小,于是将2插入到4的左边,此时有序序列变成了[2,4],无序序列变成了[8,0,5,1]。无序序列中8比4大,于是将8插入到4的右边,有序序列变成了[2,4,8],无序序列变成了[0,5,1]。以此类推,最终数组按照从小到大排序。该算法的时间复杂度为O(n^2)。

    // 插入排序
    void InsertSort(int arr[], int length)
    {
    	for (int i = 1; i < length; i++)
    	{
    		int j;
    		if (arr[i] < arr[i - 1])
    		{
    			int temp = arr[i];
    			for (j = i - 1; j >= 0 && temp < arr[j]; j--)
    			{
    				arr[j + 1] = arr[j];
    			}
    			arr[j + 1] = temp;
    		}
    	}
    }

    4、希尔排序

    希尔排序(Shell's Sort)在插入排序算法的基础上进行了改进,算法的时间复杂度与前面几种算法相比有较大的改进。其算法的基本思想是:先将待排记录序列分割成为若干子序列分别进行插入排序,待整个序列中的记录"基本有序"时,再对全体记录进行一次直接插入排序。

    // 插入排序
    void ShellSort(int arr[], int length)
    {
    	int increasement = length;
    	int i, j, k;
    	do
    	{
    		// 确定分组的增量
    		increasement = increasement / 3 + 1;
    		for (i = 0; i < increasement; i++)
    		{
    			for (j = i + increasement; j < length; j += increasement)
    			{
    				if (arr[j] < arr[j - increasement])
    				{
    					int temp = arr[j];
    					for (k = j - increasement; k >= 0 && temp < arr[k]; k -= increasement)
    					{
    						arr[k + increasement] = arr[k];
    					}
    					arr[k + increasement] = temp;
    				}
    			}
    		}
    	} while (increasement > 1);
    }

      5、快速排序

    快速排序的基本思想是:通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,已达到整个序列有序。一趟快速排序的具体过程可描述为:从待排序列中任意选取一个记录(通常选取第一个记录)作为基准值,然后将记录中关键字比它小的记录都安置在它的位置之前,将记录中关键字比它大的记录都安置在它的位置之后。这样,以该基准值为分界线,将待排序列分成的两个子序列。

    一趟快速排序的具体做法为:设置两个指针low和high分别指向待排序列的开始和结尾,记录下基准值baseval(待排序列的第一个记录),然后先从high所指的位置向前搜索直到找到一个小于baseval的记录并互相交换,接着从low所指向的位置向后搜索直到找到一个大于baseval的记录并互相交换,重复这两个步骤直到low=high为止。

    // 快速排序
    void QuickSort(int arr[], int start, int end)
    {
    	if (start >= end)
    		return;
    	int i = start;
    	int j = end;
    	// 基准数
    	int baseval = arr[start];
    	while (i < j)
    	{
    		// 从右向左找比基准数小的数
    		while (i < j && arr[j] >= baseval)
    		{
    			j--;
    		}
    		if (i < j)
    		{
    			arr[i] = arr[j];
    			i++;
    		}
    		// 从左向右找比基准数大的数
    		while (i < j && arr[i] < baseval)
    		{
    			i++;
    		}
    		if (i < j)
    		{
    			arr[j] = arr[i];
    			j--;
    		}
    	}
    	// 把基准数放到i的位置
    	arr[i] = baseval;
    	// 递归
    	QuickSort(arr, start, i - 1);
    	QuickSort(arr, i + 1, end);
    }

    6、归并排序

    “归并”的含义是将两个或两个以上的有序序列组合成一个新的有序表。假设初始序列含有n个记录,则可以看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到表示不小于x的最小整数)个长度为2(或者是1)的有序子序列,再两两归并。如此重复,直到得到一个长度为n的有序序列为止。这种排序方法称为2-路归并排序。

    // 归并排序
    void MergeSort(int arr[], int start, int end, int * temp)
    {
    	if (start >= end)
    		return;
    	int mid = (start + end) / 2;
    	MergeSort(arr, start, mid, temp);
    	MergeSort(arr, mid + 1, end, temp);
    
    	// 合并两个有序序列
    	int length = 0; // 表示辅助空间有多少个元素
    	int i_start = start;
    	int i_end = mid;
    	int j_start = mid + 1;
    	int j_end = end;
    	while (i_start <= i_end && j_start <= j_end)
    	{
    		if (arr[i_start] < arr[j_start])
    		{
    			temp[length] = arr[i_start]; 
    			length++;
    			i_start++;
    		}
    		else
    		{
    			temp[length] = arr[j_start];
    			length++;
    			j_start++;
    		}
    	}
    	while (i_start <= i_end)
    	{
    		temp[length] = arr[i_start];
    		i_start++;
    		length++;
    	}
    	while (j_start <= j_end)
    	{
    		temp[length] = arr[j_start];
    		length++;
    		j_start++;
    	}
    	// 把辅助空间的数据放到原空间
    	for (int i = 0; i < length; i++)
    	{
    		arr[start + i] = temp[i];
    	}
    }

    7、堆排序

    堆的定义如下: n个元素的序列{k1, k2, ... , kn}当且仅当满足一下条件时,称之为堆。

                    

    可以将堆看做是一个完全二叉树。并且,每个结点的值都大于等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于等于其左右孩子结点的值,称为小顶堆。

    堆排序(Heap Sort)是利用堆进行排序的方法。其基本思想为:将待排序列构造成一个大顶堆(或小顶堆),整个序列的最大值(或最小值)就是堆顶的根结点,将根节点的值和堆数组的末尾元素交换,此时末尾元素就是最大值(或最小值),然后将剩余的n-1个序列重新构造成一个堆,这样就会得到n个元素中的次大值(或次小值),如此反复执行,最终得到一个有序序列。

    /*
    	@param arr 待调整的数组
    	@param i 待调整的结点的下标
    	@param length 数组的长度
    */
    void HeapAdjust(int arr[], int i, int length)
    {
    	// 调整i位置的结点
    	// 先保存当前结点的下标
    	int max = i;
    	// 当前结点左右孩子结点的下标
    	int lchild = i * 2 + 1;
    	int rchild = i * 2 + 2;
    	if (lchild < length && arr[lchild] > arr[max])
    	{
    		max = lchild;
    	}
    	if (rchild < length && arr[rchild] > arr[max])
    	{
    		max = rchild;
    	}
    	// 若i处的值比其左右孩子结点的值小,就将其和最大值进行交换
    	if (max != i)
    	{
    		int temp;
    		temp = arr[i];
    		arr[i] = arr[max];
    		arr[max] = temp;
    		// 递归
    		HeapAdjust(arr, max, length);
    	}
    }
    
    // 堆排序
    void HeapSort(int arr[], int length)
    {
    	// 初始化堆
    	// length / 2 - 1是二叉树中最后一个非叶子结点的序号
    	for (int i = length / 2 - 1; i >= 0; i--)
    	{
    		HeapAdjust(arr, i, length);
    	}
    	// 交换堆顶元素和最后一个元素
    	for (int i = length - 1; i >= 0; i--)
    	{
    		int temp;
    		temp = arr[i];
    		arr[i] = arr[0];
    		arr[0] = temp;
    		HeapAdjust(arr, 0, i);
    	}
    }

     

    展开全文
  • 经典九大排序(1)——简单排序

    万次阅读 多人点赞 2019-05-11 16:19:25
    九大排序排序是数据结构体系中最重要的内容之一,这一块必须要非常熟练的掌握,应该做到可以立马写出每个排序的代码,有多种实现方法的必须多种都能很快写出来,当然对各个排序的性能的了解也是基础且重要的。...

    本博客已弃用,当时存在一些小细节错误后期也不再修改了

    欢迎来我的新博客

    九大排序排序是数据结构体系中最重要的内容之一,这一块必须要非常熟练的掌握,应该做到可以立马写出每个排序的代码,有多种实现方法的必须多种都能很快写出来,当然对各个排序的性能的了解也是基础且重要的。我们先对排序这一块进行一个整体的把握。

        这里先说明几个概念

    • 内排序:在对待排序数据存放在内存中进行的排序过程。是我们主要讨论与学习的重点。
    • 外排序:待排数据量太大,无法一次性将所有待排序数据放入内存中,在排序过程中需要对磁盘等外部储存器进行访问。不是我们谈论与学习的重点,但也要通过相关资料或书籍了解其基本原理。
    • 比较排序:排序过程中需要对数据关键字进行比较。
    • 非比较排序:排序过程中不需要对数据关键字进行比较。
    • 排序算法的稳定性:在每一次单趟排序后,相同关键字的相对顺序不变。(后面讲到了再具体解释)

    所有讲解都以升序为例(降序完全就是改个符号的问题啦),本篇先讲几个简单的,复杂些的后面每个单独写。


    直接插入排序

    直接插入排序是非常简单的,对于一个长度为n的关键字序列a1,a2,a3,a4,a5...an, 一句话来说:我们就是要把每个关键字都放到其之前的有序子序列中的合适位置。

    具体是这样:你看,该序列的第一个元素a1之前不存在子序列因此不用考虑,故从第二个元素开始,先把a2的值保存到Key中,那么此时,a2如果大于等于a1,那么a2就不动,因为这就是它当前合适的位置,若是a2小于a1那么就把a1往后挪一个,把a2放到a1的位置。

    对于一般的情况是这样:

    在有序子序列中从后往前找,直到找到一个key小于等于key的数(每往前找一个,那么就往后挪一个),把key放在这个数后面,这就是key合适的位置(好好想明白),或者可能找完了整个序列也没找到我们要的合适的位置,那就放在该有序子序列的第一个元素的位置(此时有序子序列的所有元素已经后挪),同样,你想想,若有序子序列的最后一个元素就小于key,那么就不用挪了,当前的位置就是合适的位置。

    那么接下来

            

    当然,更常见的情况是这样,并不是简单的是需要移动多次的,但是没关系,核心思想都是一样的

    前面四个关键字都调整好了,那么第五个呢?看到这你肯定心中有答案了

    代码

    void InsertSort(int* a,int len)
    {
        int begin = 1;
        int i = 0;
        while(begin < len)
        {
            int key = a[begin];
            for(i = begin-1;i>=0;i--)
            {
                if(a[i]<=key)    //稳定的
                {
                    a[i+1] = key;
                    break;
                }
                a[i+1] = a[i];
            }
            if(i<0)
                a[0] = key;//说明找完了整个有序子序列都没找到
            begin++;
        }
    }

    其实在找关键字key合适位置时,从有序子序列前往后也是可以的,从时间复杂度上一样的,但是个人认为从后往前扫描的代码写出来非常简洁。

    算法分析

    • 平均时间复杂度:o(N^2)这是显然的,标准的内外两层循环
    • 最好时间复杂度:o(N),如果有序,那么每个元素都已经在在它的待排子序列的合适位置,不用找合适位置
    • 最坏时间复杂度:o(N^2)
    • 空间复杂度:o(1),因为需要常熟个临时变量
    • 稳定性:稳定的

    有人提出在定位关键字的合适位置的时候用二分查找,正好可以利用前面排好的结果(就是在把每个关键字放入到其前面的有序子序列中合适位置时,未必要一个个比较着来找,因为有序子序列是有序的,那么很自然的就可以想到用二分查找来降低时间复杂度),这样每次查找合适位置的时间复杂度就由o(n)降低到了o(log2n)了,但是对于找到后的插入这一操作,还是得挨个挪动数据,仍然为o(n)。这就很尴尬了,你会发现整体的时间复杂度还是o(n^2),并没有用,查找能快又怎么样呢,还是得一个一个挪数据,所以,普通的直接插入排序是没法再优化了。


    希尔排序

        希尔排序是一个叫希尔的数学家提出的一种优化版本直接插入排序

        有必要先谈谈这个排序是怎么来的(主要基于以下两点)

    1. 在直接插入排序里,对于一组已经有序的关键字序列进行排序时间复杂度是o(n),因为每个元素的合适位置的查找都只需一次就能找到,因为左边的有序子序列的最后一个就小于等于该元素,那么就不需要挪动任何元素,每一趟都只用比较一次就结束了单趟排序。
    2. 放宽第一点的情况,我们不要求有序,其实只要待排序列的有序度越高,也就是逆序对越少,直接插入排序的时间复杂度肯定是越低的(这句话是希尔排序的核心)。

    基于这两点希尔对直接插入排序进行了这样的优化:先将待排序列分为若干个稀疏的子序列(后面解释),对这些子序列分别进行直接插入排序。经过这一番调整,整个序列的有序度一定会被提高,逆序对一定会变少。最后,再对整个序列进行一趟直接插入排序。

    首先选定子序列中各元素的距离d_i,使待排数据中所有间距为为d_i的数据被分成了一组,在各个组内进行直接插入排序,直到\bg_white \fn_phv d_i=1。此时我们最后一趟进行的就相当于一次完整的(但是效率很高的)直接插入排序。

        过程如下

    需要注意的是,虽然每次是对各组进行插入排序,但是写代码时候的思维当然不是直接单独对每个组那样直接插入排序依次,而仍然是从前往后扫描,那么显然,我们每次直接插入排序的key从每次的第一个子序列的第二个元素开始(与直接插入排序同理),然后挨个往后走,每个元素时属于哪个组,我们就把它在其所在组进行直接插入排序,上面的例子中,第一次排序中,我们实际进行时就是从94开始往后走的,第二次排序中,我们就是从05开始的,这样代码就非常好写了。

    void ShellSort(int* a,int len)
    {
        int gap = len;                                                                                                                          
        while(gap > 1)
        {   
            gap = gap/3 + 1;
            for(int i = gap;i < len;i++)
            {   
                int key = a[i];
                int start = i - gap;
                while(start >= 0 && key <= a[start])//对当前key进行一趟直接插入排序
                {   
                    a[start+gap] = a[start];
                    start -= gap;
                }   
                a[start + gap] = key;
            }   
        }   
    }

    希尔排序的时间复杂度相当不好分析,因为其时间复杂度很大程度上取决于增量序列d_i,而d_i的选取至今也没有人找出怎样的一个增量序列是对所有情况的数据分布都有非常不错的效率,我们在代码中选取gap/3+1是一种较为常用、对于大部分数据分布的平均时间复杂度都较为不错的增量序列。

    算法分析

    • 平均时间复杂度:o(N^1.3),大量数据研究表明在o(N^1.3)附近,事实上也不是严格论证的结果
    • 最好时间复杂度:仍然和增量序列的选取有关
    • 最坏时间复杂度:o(N^2)
    • 空间复杂度:o(1)
    • 稳定性:不稳定,例如待排序列(3,2,2,1),取d=2时,显然就能看出是不稳定的

    简单选择排序

    简单选择排序是真的相当简单了,其思想概括来说就是每趟从当前待排序列中选出最小的放在已拍好序列的末尾

    指针i 记录待排序列的第一个的元素,指针k用来找待排序列中最小的那个元素,k当然是从i开始,遍历待排序列一趟后,把指针k指向的元素与指针i指向的元素交换,因为待排序列中又少了一个元素,已排序列末尾又多了一个,因此i往后走一个,如此知道待排序列中只剩下一个元素。

    这显然效率太低了点,我们忘了它吧。有个明显可以做的优化就是我们每趟遍历可以找出待排序序列中最小和最大的两个,放在待排序列两端,然后缩小待排序列,如此循环直到当前待排序列中只有一个元素。这样效率肯定能稍微好一些,但无疑仍然是平方级的时间复杂度。

    代码

    void SelectSort(int* a,size_t len)
    {
        int begin = 0;
        int end = len - 1;
        int max = 0;
        int min = 0;
        while(begin < end)
        {
            max = begin,min = begin;
            for(int i = begin;i <= end;i++)
            {
                if(a[i]>=a[max])  //有相同元素时,最大的要找位置相对最后的一个最大的
                {
                    max = i;
                }
                if(a[i]<a[min])  //最小的要找位置相对最前的一个最小的,这样可以使选择排序算法稳定
                {
                    min = i;
                }
            }
            if(max == begin && min == end)
            {
                swap(a[max],a[end]);
                continue;
            }
    
            if(max == begin)
            {
                swap(a[max],a[end]);
                swap(a[min],a[begin]);
                continue;
            }
    
            if(min == end)
            {
                swap(a[min],a[begin]);
                swap(a[max],a[end]);
                continue;
            }
            swap(a[min],a[begin]);
            swap(a[max],a[end]);
            begin++;
            end--;
        } 
    }

    注意:找到当前待排序列最大、最小的元素后,要判断是否为最小的在最后,最大的在最前这些情况的组合,稍微分析下就能知道应该怎么交换才是合适的。

    算法分析

    • 平均时间复杂度:o(N^2),嵌套双循环
    • 最好时间复杂度:o(N^2),每次要找最大最小肯定是要遍历一遍的
    • 最坏时间复杂度:o(N^2)
    • 空间复杂度:o(1)
    • 稳定性:稳定的(在注释中已解释)

    冒泡排序

    这应该是所有人在没系统的学习数据结构前就已经熟知的排序算法,它也很简单,而且它的名字非常形象,冒泡排序的思想就是每一趟排序都把大的元素往上浮,具体是这样:从当前待排序列第一个开始遍历,指针从第一个开始,如果当前元素大于下一个,那么二者交换,指针往后走,当走到待排序列末尾时,最大的一定被放到了最后(像冒泡泡一样上去了),然后缩小待排子序列(把最后一个从当前待排序序列删去),如此循环直到当前待排子序列只有一个元素。

    有一定可以明显优化的是,如果在某次单趟排序中没有发生元素的交换,可以说明整个待排序列已经有序

    代码

    void BubbleSort(int* a,size_t len)
    {
        int end = len-1;
        while(end > 0)
        {
            bool exchange = false;
            for(int i = 0;i < end;i++)
            {
                if(a[i]>a[i+1])
                {
                swap(a[i],a[i+1]);
                exchange = true;
                }
            }
            if(exchange == false)
                return;
            else
                exchange = false;
            end--;
        }
    }

    算法分析

    • 平均时间复杂度:o(N^2),嵌套双循环
    • 最好时间复杂度:o(N),若已经有序,那么第一趟就排好了
    • 最坏时间复杂度:o(N^2)
    • 空间复杂度:o(1)
    • 稳定性:稳定的(在注释中已解释)

     

    展开全文
  • 八大排序算法原理及实现

    万次阅读 多人点赞 2018-08-10 22:24:10
    排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说八大排序就是内部排序。    当n较大...

    概述

    排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。

    我们这里说说八大排序就是内部排序。

        

        当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序。

       快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;


     

    1.插入排序—直接插入排序(Straight Insertion Sort)

    基本思想:

    将一个记录插入到已排序好的有序表中,从而得到一个新,记录数增1的有序表。即:先将序列的第1个记录看成是一个有序的子序列,然后从第2个记录逐个进行插入,直至整个序列有序为止。

    要点:设立哨兵,作为临时存储和判断数组边界之用。

    直接插入排序示例:

     

     

     

    如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

    算法的实现:

    #include <iostream>
    using namespace std;
    
    void Print(int a[], int n, int i) {
    	cout << i << ":";
    	for (int j = 0; j<8; j++) {
    		cout << a[j] << " ";
    	}
    	cout << endl;
    }
    
    
    void InsertSort(int a[], int n)
    {
    	for (int i = 1; i<n; i++) {
    		if (a[i] < a[i - 1]) {               //若第i个元素大于i-1元素,直接插入。小于的话,移动有序表后插入  
    			int j = i - 1;
    			int x = a[i];        //复制为哨兵,即存储待排序元素  
    			a[i] = a[i - 1];           //先后移一个元素  
    			while (x < a[j]) {  //查找在有序表的插入位置  
    				a[j + 1] = a[j];
    				j--;         //元素后移  
    			}
    			a[j + 1] = x;      //插入到正确位置  
    		}
    		Print(a, n, i);           //打印每趟排序的结果  
    	}
    
    }
    
    int main() {
    	int a[8] = { 3,1,5,7,2,4,9,6 };
    	InsertSort(a, 8);
    	Print(a, 8, 8);
    }

    输出:

     

    效率:

    时间复杂度:O(n^2).

    其他的插入排序有二分插入排序,2-路插入排序。

     

     2. 插入排序—希尔排序(Shell`s Sort)

    希尔排序是1959 年由D.L.Shell 提出来的,相对直接排序有较大的改进。希尔排序又叫缩小增量排序

    基本思想:

    先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。

    操作方法:

    1. 选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;
    2. 按增量序列个数k,对序列进行k 趟排序;
    3. 每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

    希尔排序的示例:

     

    算法实现:

     

    我们简单处理增量序列:增量序列d = {n/2 ,n/4, n/8 .....1} n为要排序数的个数

    即:先将要排序的一组记录按某个增量d(n/2,n为要排序数的个数)分成若干组子序列,每组中记录的下标相差d.对每组中全部元素进行直接插入排序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。继续不断缩小增量直至为1,最后使用直接插入排序完成排序。

    #include <iostream>  
    using namespace std;
    
    void Print(int a[], int n, int i) {
    	cout << i << ":";
    	for (int j = 0; j<8; j++) {
    		cout << a[j] << " ";
    	}
    	cout << endl;
    }
    /**
    * 直接插入排序的一般形式
    *
    * @param int dk 缩小增量,如果是直接插入排序,dk=1
    *
    */
    
    void ShellInsertSort(int a[], int n, int dk)
    {
    	for (int i = dk; i<n; ++i) {
    		if (a[i] < a[i - dk]) {          //若第i个元素大于i-1元素,直接插入。小于的话,移动有序表后插入  
    			int j = i - dk;
    			int x = a[i];           //复制为哨兵,即存储待排序元素  
    			a[i] = a[i - dk];         //首先后移一个元素  
    			while (j >= 0 && x < a[j]) {     //查找在有序表的插入位置  
    				a[j + dk] = a[j];
    				j -= dk;             //元素后移  
    			}
    			a[j + dk] = x;            //插入到正确位置  
    		}
    		Print(a, n, i);
    	}
    
    }
    
    /**
    * 先按增量d(n/2,n为要排序数的个数进行希尔排序
    *
    */
    void ShellSort(int a[], int n) {
    
    	int dk = n / 2;
    	while (dk >= 1) {
    		ShellInsertSort(a, n, dk);
    		dk = dk / 2;
    	}
    }
    int main() {
    	int a[8] = { 3,1,5,7,2,4,9,6 };
    	//ShellInsertSort(a,8,1); //直接插入排序  
    	ShellSort(a, 8);           //希尔插入排序  
    	Print(a, 8, 8);
    }

    输出:

    希尔排序时效分析很难,关键码的比较次数与记录移动次数依赖于增量因子序列d的选取,特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法,有取奇数的,也有取质数的,但需要注意:增量因子中除1 外没有公因子,且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。

     

    3. 选择排序—简单选择排序(Simple Selection Sort)

    基本思想:

    在要排序的一组数中,选出最小(或者最大)的一个数与第1个位置的数交换;然后在剩下的数当中再找最小(或者最大)的与第2个位置的数交换,依次类推,直到第n-1个元素(倒数第二个数)和第n个元素(最后一个数)比较为止。

    简单选择排序的示例:

     

    操作方法:

    第一趟,从n 个记录中找出关键码最小的记录与第一个记录交换;

    第二趟,从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换;

    以此类推.....

    第i 趟,则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换,

    直到整个序列按关键码有序。

     

    算法实现:

    #include <iostream>
    using namespace std;
    
    void Print(int a[], int n, int i) {
    	cout << "第" << i + 1 << "趟 : ";
    	for (int j = 0; j<8; j++) {
    		cout << a[j] << "  ";
    	}
    	cout << endl;
    }
    /**
    * 数组的最小值
    *
    * @return int 数组的键值
    */
    int SelectMinKey(int a[], int n, int i)
    {
    	int k = i;
    	for (int j = i + 1; j< n; ++j) {
    		if (a[k] > a[j]) k = j;
    	}
    	return k;
    }
    
    /**
    * 选择排序
    *
    */
    void SelectSort(int a[], int n) {
    	int key, tmp;
    	for (int i = 0; i < n - 1; ++i) {
    		key = SelectMinKey(a, n, i);           //选择最小的元素  
    		if (key != i) {
    			tmp = a[i];  a[i] = a[key]; a[key] = tmp; //最小元素与第i位置元素互换  
    		}
    		Print(a, n, i);
    	}
    }
    int main() {
    	int a[8] = { 3,1,5,7,2,4,9,6 };
    	cout << "初始值:";
    	for (int j = 0; j<8; j++) {
    		cout << a[j] << "  ";
    	}
    	cout << endl << endl;
    	SelectSort(a, 8);
    	Print(a, 8, 8);
    }

     输出:

    简单选择排序的改进——二元选择排序

     

    简单选择排序,每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素(当前趟最大和最小记录)的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序,最多只需进行[n/2]趟循环即可。具体实现如下:

    #include <iostream>
    using namespace std;
    
    void Print(int *arr, int n, int i) {
    	cout << i << ": ";
    	for (int j = 0; j < n; ++j) {
    		cout << arr[j] << " ";
    	}
    	cout << endl;
    }
    
    void SelectSort(int *arr, int n) {
    	int i = 0, j = 0, min = 0, max = 0, tmp = 0;
    	for (i = 1; i <= n / 2; i++) {
    		// 做不超过n/2趟选择排序   
    		min = i; max = i; //分别记录最大和最小关键字记录位置  
    		for (j = i + 1; j <= n - i; j++) {
    			if (arr[j] > arr[max]) {
    				max = j; continue;
    			}
    			if (arr[j] < arr[min]) {
    				min = j;
    			}
    		}
    		//该交换操作还可分情况讨论以提高效率  
    		tmp = arr[i - 1]; arr[i - 1] = arr[min]; arr[min] = tmp;
    		tmp = arr[n - i]; arr[n - i] = arr[max]; arr[max] = tmp;
    
    	}
    }
    int main()
    {
    	int arr[10] = { 5,9,6,2,1,4,7,3,8,0 };
    	SelectSort(arr, 10);
    	Print(arr, 10, 10);
    	return 0;
    }

    输出:

    4. 选择排序—堆排序(Heap Sort)

    堆排序是一种树形选择排序,是对直接选择排序的有效改进。

    基本思想:

     

    堆的定义如下:具有n个元素的序列(k1,k2,...,kn),当且仅当满足

     

    时称之为堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)。
    若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的。如:

     

    (a)大顶堆序列:(96, 83,27,38,11,09)

      (b)  小顶堆序列:(12,36,24,85,47,30,53,91)

     

    初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树(一维数组存储二叉树),调整它们的存储序,使之成为一个堆,将堆顶元素输出,得到n 个元素中最小(或最大)的元素,这时堆的根节点的数最小(或者最大)。然后对前面(n-1)个元素重新调整使之成为堆,输出堆顶元素,得到n 个元素中次小(或次大)的元素。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。称这个过程为堆排序

    因此,实现堆排序需解决两个问题:
    1. 如何将n 个待排序的数建成堆;
    2. 输出堆顶元素后,怎样调整剩余n-1 个元素,使其成为一个新堆。


    首先讨论第二个问题:输出堆顶元素后,对剩余n-1元素重新建成堆的调整过程。
    调整小顶堆的方法:

    1)设有m 个元素的堆,输出堆顶元素后,剩下m-1 个元素。将堆底元素送入堆顶((最后一个元素与堆顶进行交换),堆被破坏,其原因仅是根结点不满足堆的性质。

    2)将根结点与左、右子树中较小元素的进行交换。

    3)若与左子树交换:如果左子树堆被破坏,即左子树的根结点不满足堆的性质,则重复方法 (2).

    4)若与右子树交换,如果右子树堆被破坏,即右子树的根结点不满足堆的性质。则重复方法 (2).

    5)继续对不满足堆性质的子树进行上述交换操作,直到叶子结点,堆被建成。

    称这个自根结点到叶子结点的调整过程为筛选。如图:


    再讨论对n 个元素初始建堆的过程。
    建堆方法:对初始序列建堆的过程,就是一个反复进行筛选的过程。

    1)n 个结点的完全二叉树,则最后一个结点是第个结点的子树。

    2)筛选从第个结点为根的子树开始,该子树成为堆。

    3)之后向前依次对各结点为根的子树进行筛选,使之成为堆,直到根结点。

    如图建堆初始过程:无序序列:(49,38,65,97,76,13,27,49)
                                  


                                  

     

     算法的实现:

    从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。

    [cpp] view plain copy

    1. void print(int a[], int n){  
    2.     for(int j= 0; j<n; j++){  
    3.         cout<<a[j] <<"  ";  
    4.     }  
    5.     cout<<endl;  
    6. }  
    7.   
    8.   
    9.   
    10. /** 
    11.  * 已知H[s…m]除了H[s] 外均满足堆的定义 
    12.  * 调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选,  
    13.  * 
    14.  * @param H是待调整的堆数组 
    15.  * @param s是待调整的数组元素的位置 
    16.  * @param length是数组的长度 
    17.  * 
    18.  */  
    19. void HeapAdjust(int H[],int s, int length)  
    20. {  
    21.     int tmp  = H[s];  
    22.     int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)  
    23.     while (child < length) {  
    24.         if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)  
    25.             ++child ;  
    26.         }  
    27.         if(H[s]<H[child]) {  // 如果较大的子结点大于父结点  
    28.             H[s] = H[child]; // 那么把较大的子结点往上移动,替换它的父结点  
    29.             s = child;       // 重新设置s ,即待调整的下一个结点的位置  
    30.             child = 2*s+1;  
    31.         }  else {            // 如果当前待调整结点大于它的左右孩子,则不需要调整,直接退出  
    32.              break;  
    33.         }  
    34.         H[s] = tmp;         // 当前待调整的结点放到比其大的孩子结点位置上  
    35.     }  
    36.     print(H,length);  
    37. }  
    38.   
    39.   
    40. /** 
    41.  * 初始堆进行调整 
    42.  * 将H[0..length-1]建成堆 
    43.  * 调整完之后第一个元素是序列的最小的元素 
    44.  */  
    45. void BuildingHeap(int H[], int length)  
    46. {   
    47.     //最后一个有孩子的节点的位置 i=  (length -1) / 2  
    48.     for (int i = (length -1) / 2 ; i >= 0; --i)  
    49.         HeapAdjust(H,i,length);  
    50. }  
    51. /** 
    52.  * 堆排序算法 
    53.  */  
    54. void HeapSort(int H[],int length)  
    55. {  
    56.     //初始堆  
    57.     BuildingHeap(H, length);  
    58.     //从最后一个元素开始对序列进行调整  
    59.     for (int i = length - 1; i > 0; --i)  
    60.     {  
    61.         //交换堆顶元素H[0]和堆中最后一个元素  
    62.         int temp = H[i]; H[i] = H[0]; H[0] = temp;  
    63.         //每次交换堆顶元素和堆中最后一个元素之后,都要对堆进行调整  
    64.         HeapAdjust(H,0,i);  
    65.   }  
    66. }   
    67.   
    68. int main(){  
    69.     int H[10] = {3,1,5,7,2,4,9,6,10,8};  
    70.     cout<<"初始值:";  
    71.     print(H,10);  
    72.     HeapSort(H,10);  
    73.     //selectSort(a, 8);  
    74.     cout<<"结果:";  
    75.     print(H,10);  
    76.   
    77. }  

     

     

    分析:

     

     

    设树深度为k,。从根到叶的筛选,元素比较次数至多2(k-1)次,交换记录至多k 次。所以,在建好堆后,排序过程中的筛选次数不超过下式: 

                                    

    而建堆时的比较次数不超过4n 次,因此堆排序最坏情况下,时间复杂度也为:O(nlogn )。

     

    5. 交换排序—冒泡排序(Bubble Sort)

    基本思想:

    在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。

    冒泡排序的示例:

     

    算法的实现:

    #include <iostream>
    using namespace std;
    
    void Print(int *arr, int n, int i) {
    	cout << i << ": ";
    	for (int j = 0; j < n; ++j) {
    		cout << arr[j] << " ";
    	}
    	cout << endl;
    }
    
    void BubbleSort(int *arr, int n) {
    	for (int i = 0; i < n - 1; ++i) {
    		for (int j = 0; j < n - i - 1; ++j) {
    			if (arr[j] > arr[j + 1])
    			{
    				int tmp = arr[j];
    				arr[j] = arr[j + 1]; 
    				arr[j + 1] = tmp;
    			}
    		}
    		Print(arr, 10, i);
    	}
    }
    
    int main()
    {
    	int arr[10] = { 5,9,6,2,1,4,7,3,8,0 };
    	BubbleSort(arr, 10);
    	Print(arr, 10, 10);
    
    	return 0;
    }

    输出:

    冒泡排序算法的改进

    对冒泡排序常见的改进方法是加入一标志性变量exchange,用于标志某一趟排序过程中是否有数据交换,如果进行某一趟排序时并没有进行数据交换,则说明数据已经按要求排列好,可立即结束排序,避免不必要的比较过程。本文再提供以下两种改进算法:

    1.设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。

    改进后算法如下:

    [cpp] view plain copy

    1. void Bubble_1 ( int r[], int n) {  
    2.     int i= n -1;  //初始时,最后位置保持不变  
    3.     while ( i> 0) {   
    4.         int pos= 0; //每趟开始时,无记录交换  
    5.         for (int j= 0; j< i; j++)  
    6.             if (r[j]> r[j+1]) {  
    7.                 pos= j; //记录交换的位置   
    8.                 int tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;  
    9.             }   
    10.         i= pos; //为下一趟排序作准备  
    11.      }   
    12. }    

     

    2.传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

     

    改进后的算法实现为:

    [cpp] view plain copy

    1. void Bubble_2 ( int r[], int n){  
    2.     int low = 0;   
    3.     int high= n -1; //设置变量的初始值  
    4.     int tmp,j;  
    5.     while (low < high) {  
    6.         for (j= low; j< high; ++j) //正向冒泡,找到最大者  
    7.             if (r[j]> r[j+1]) {  
    8.                 tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;  
    9.             }   
    10.         --high;                 //修改high值, 前移一位  
    11.         for ( j=high; j>low; --j) //反向冒泡,找到最小者  
    12.             if (r[j]<r[j-1]) {  
    13.                 tmp = r[j]; r[j]=r[j-1];r[j-1]=tmp;  
    14.             }  
    15.         ++low;                  //修改low值,后移一位  
    16.     }   
    17. }   

     

    6. 交换排序—快速排序(Quick Sort)

     

    基本思想:

    1)选择一个基准元素,通常选择第一个元素或者最后一个元素,

    2)通过一趟排序讲待排序的记录分割成独立的两部分,其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。

    3)此时基准元素在其排好序后的正确位置

    4)然后分别对这两部分记录用同样的方法继续进行排序,直到整个序列有序。

    快速排序的示例:

    (a)一趟排序的过程:

    (b)排序的全过程

    算法的实现:

     递归实现:

    #include <iostream>
    using namespace std;
    
    void print(int a[], int n) {
    	for (int j = 0; j<n; j++) {
    		cout << a[j] << "  ";
    	}
    	cout << endl;
    }
    
    void swap(int *a, int *b)
    {
    	int tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    
    int partition(int a[], int low, int high)
    {
    	int privotKey = a[low];                             //基准元素
    	while (low < high) {                                   //从表的两端交替地向中间扫描
    
    
    		while (low < high  && a[high] >= privotKey) --high;  //从high 所指位置向前搜索,至多到low+1 位置。将比基准元素小的交换到低端
    		swap(&a[low], &a[high]);
    
    		while (low < high  && a[low] <= privotKey) ++low;
    		swap(&a[low], &a[high]);
    
    	}
    	print(a, 10);
    	return low;
    }
    
    
    void quickSort(int a[], int low, int high) {
    	if (low < high) {
    		int privotLoc = partition(a, low, high);  //将表一分为二
    		quickSort(a, low, privotLoc - 1);          //递归对低子表递归排序
    		quickSort(a, privotLoc + 1, high);        //递归对高子表递归排序
    	}
    }
    
    int main() {
    	int a[10] = { 3,1,5,7,2,4,9,6,10,8 };
    	cout << "初始值:";
    	print(a, 10);
    	quickSort(a, 0, 9);
    	cout << "结果:";
    	print(a, 10);
    
    	return 0;
    }

    输出:

    分析:

    快速排序是通常被认为在同数量级(O(nlog2n))的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时,快排序反而蜕化为冒泡排序。为改进之,通常以“三者取中法”来选取基准记录,即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。

     
    快速排序的改进

    在本改进算法中,只对长度大于k的子序列递归调用快速排序,让原序列基本有序,然后再对整个基本有序序列用插入排序算法排序。实践证明,改进后的算法时间复杂度有所降低,且当k取值为 8 左右时,改进算法的性能最佳。算法思想如下:

    [cpp] view plain copy

    1. void print(int a[], int n){  
    2.     for(int j= 0; j<n; j++){  
    3.         cout<<a[j] <<"  ";  
    4.     }  
    5.     cout<<endl;  
    6. }  
    7.   
    8. void swap(int *a, int *b)  
    9. {  
    10.     int tmp = *a;  
    11.     *a = *b;  
    12.     *b = tmp;  
    13. }  
    14.   
    15. int partition(int a[], int low, int high)  
    16. {  
    17.     int privotKey = a[low];                 //基准元素  
    18.     while(low < high){                   //从表的两端交替地向中间扫描  
    19.         while(low < high  && a[high] >= privotKey) --high; //从high 所指位置向前搜索,至多到low+1 位置。将比基准元素小的交换到低端  
    20.         swap(&a[low], &a[high]);  
    21.         while(low < high  && a[low] <= privotKey ) ++low;  
    22.         swap(&a[low], &a[high]);  
    23.     }  
    24.     print(a,10);  
    25.     return low;  
    26. }  
    27.   
    28.   
    29. void qsort_improve(int r[ ],int low,int high, int k){  
    30.     if( high -low > k ) { //长度大于k时递归, k为指定的数  
    31.         int pivot = partition(r, low, high); // 调用的Partition算法保持不变  
    32.         qsort_improve(r, low, pivot - 1,k);  
    33.         qsort_improve(r, pivot + 1, high,k);  
    34.     }   
    35. }   
    36. void quickSort(int r[], int n, int k){  
    37.     qsort_improve(r,0,n,k);//先调用改进算法Qsort使之基本有序  
    38.   
    39.     //再用插入排序对基本有序序列排序  
    40.     for(int i=1; i<=n;i ++){  
    41.         int tmp = r[i];   
    42.         int j=i-1;  
    43.         while(tmp < r[j]){  
    44.             r[j+1]=r[j]; j=j-1;   
    45.         }  
    46.         r[j+1] = tmp;  
    47.     }   
    48.   
    49. }   
    50.   
    51.   
    52.   
    53. int main(){  
    54.     int a[10] = {3,1,5,7,2,4,9,6,10,8};  
    55.     cout<<"初始值:";  
    56.     print(a,10);  
    57.     quickSort(a,9,4);  
    58.     cout<<"结果:";  
    59.     print(a,10);  
    60.   
    61. }  

     

    7. 归并排序(Merge Sort)

     

    基本思想:

    归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

    归并排序示例:

     

     

    合并方法:

    设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成,两个子表长度分别为n-i +1、n-m。

    1. j=m+1;k=i;i=i; //置两个子表的起始下标及辅助数组的起始下标
    2. 若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束
    3. //选取r[i]和r[j]较小的存入辅助数组rf
      如果r[i]<r[j],rf[k]=r[i]; i++; k++; 转⑵
      否则,rf[k]=r[j]; j++; k++; 转⑵
    4. //将尚未处理完的子表中元素存入rf
      如果i<=m,将r[i…m]存入rf[k…n] //前一子表非空
      如果j<=n ,  将r[j…n] 存入rf[k…n] //后一子表非空
    5. 合并结束。

    [cpp] view plain copy

    1. //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]  
    2. void Merge(ElemType *r,ElemType *rf, int i, int m, int n)  
    3. {  
    4.     int j,k;  
    5.     for(j=m+1,k=i; i<=m && j <=n ; ++k){  
    6.         if(r[j] < r[i]) rf[k] = r[j++];  
    7.         else rf[k] = r[i++];  
    8.     }  
    9.     while(i <= m)  rf[k++] = r[i++];  
    10.     while(j <= n)  rf[k++] = r[j++];  
    11. }  

     

     

    归并的迭代算法

     

    1 个元素的表总是有序的。所以对n 个元素的待排序列,每个元素可看成1 个有序子表。对子表两两合并生成n/2个子表,所得子表除最后一个子表长度可能为1 外,其余子表长度均为2。再进行两两合并,直到生成n 个元素按关键码有序的表。

    [cpp] view plain copy

    1. void print(int a[], int n){  
    2.     for(int j= 0; j<n; j++){  
    3.         cout<<a[j] <<"  ";  
    4.     }  
    5.     cout<<endl;  
    6. }  
    7.   
    8. //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]  
    9. void Merge(ElemType *r,ElemType *rf, int i, int m, int n)  
    10. {  
    11.     int j,k;  
    12.     for(j=m+1,k=i; i<=m && j <=n ; ++k){  
    13.         if(r[j] < r[i]) rf[k] = r[j++];  
    14.         else rf[k] = r[i++];  
    15.     }  
    16.     while(i <= m)  rf[k++] = r[i++];  
    17.     while(j <= n)  rf[k++] = r[j++];  
    18.     print(rf,n+1);  
    19. }  
    20.   
    21. void MergeSort(ElemType *r, ElemType *rf, int lenght)  
    22. {   
    23.     int len = 1;  
    24.     ElemType *q = r ;  
    25.     ElemType *tmp ;  
    26.     while(len < lenght) {  
    27.         int s = len;  
    28.         len = 2 * s ;  
    29.         int i = 0;  
    30.         while(i+ len <lenght){  
    31.             Merge(q, rf,  i, i+ s-1, i+ len-1 ); //对等长的两个子表合并  
    32.             i = i+ len;  
    33.         }  
    34.         if(i + s < lenght){  
    35.             Merge(q, rf,  i, i+ s -1, lenght -1); //对不等长的两个子表合并  
    36.         }  
    37.         tmp = q; q = rf; rf = tmp; //交换q,rf,以保证下一趟归并时,仍从q 归并到rf  
    38.     }  
    39. }  
    40.   
    41.   
    42. int main(){  
    43.     int a[10] = {3,1,5,7,2,4,9,6,10,8};  
    44.     int b[10];  
    45.     MergeSort(a, b, 10);  
    46.     print(b,10);  
    47.     cout<<"结果:";  
    48.     print(a,10);  
    49.   
    50. }  

     

    两路归并的递归算法

     

    [cpp] view plain copy

    1. void MSort(ElemType *r, ElemType *rf,int s, int t)  
    2. {   
    3.     ElemType *rf2;  
    4.     if(s==t) r[s] = rf[s];  
    5.     else  
    6.     {   
    7.         int m=(s+t)/2;          /*平分*p 表*/  
    8.         MSort(r, rf2, s, m);        /*递归地将p[s…m]归并为有序的p2[s…m]*/  
    9.         MSort(r, rf2, m+1, t);      /*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/  
    10.         Merge(rf2, rf, s, m+1,t);   /*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/  
    11.     }  
    12. }  
    13. void MergeSort_recursive(ElemType *r, ElemType *rf, int n)  
    14. {   /*对顺序表*p 作归并排序*/  
    15.     MSort(r, rf,0, n-1);  
    16. }  

    8. 桶排序/基数排序(Radix Sort)

    说基数排序之前,我们先说桶排序:

    基本思想:是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。
             简单来说,就是把数据分组,放在一个个的桶中,然后对每个桶里面的在进行排序。  

     

     例如要对大小为[1..1000]范围内的n个整数A[1..n]排序  

     首先,可以把桶设为大小为10的范围,具体而言,设集合B[1]存储[1..10]的整数,集合B[2]存储   (10..20]的整数,……集合B[i]存储(   (i-1)*10,   i*10]的整数,i   =   1,2,..100。总共有  100个桶。  

      然后,对A[1..n]从头到尾扫描一遍,把每个A[i]放入对应的桶B[j]中。  再对这100个桶中每个桶里的数字排序,这时可用冒泡,选择,乃至快排,一般来说任  何排序法都可以。

      最后,依次输出每个桶里面的数字,且每个桶中的数字从小到大输出,这  样就得到所有数字排好序的一个序列了。  

      假设有n个数字,有m个桶,如果数字是平均分布的,则每个桶里面平均有n/m个数字。如果  

      对每个桶中的数字采用快速排序,那么整个算法的复杂度是  

      O(n   +   m   *   n/m*log(n/m))   =   O(n   +   nlogn   -   nlogm)  

      从上式看出,当m接近n的时候,桶排序复杂度接近O(n)  

      当然,以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的  ,实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中,那就退化成一般的排序了。  

            前面说的几大排序算法 ,大部分时间复杂度都是O(n2),也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O(n)的时间复杂度。但桶排序的缺点是:

            1)首先是空间复杂度比较高,需要的额外开销大。排序有两个数组的空间开销,一个存放待排序数组,一个就是所谓的桶,比如待排序值是从0到m-1,那就需要m个桶,这个桶数组就要至少m个空间。

            2)其次待排序的元素都要在一定的范围内等等。

           桶式排序是一种分配排序。分配排序的特定是不需要进行关键码的比较,但前提是要知道待排序列的一些具体情况。

     

    分配排序的基本思想:说白了就是进行多次的桶式排序。

    基数排序过程无须比较关键字,而是通过“分配”和“收集”过程来实现排序。它们的时间复杂度可达到线性阶:O(n)。

    实例:

    扑克牌中52 张牌,可按花色和面值分成两个字段,其大小关系为:
    花色: 梅花< 方块< 红心< 黑心  
    面值: 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < 10 < J < Q < K < A

    若对扑克牌按花色、面值进行升序排序,得到如下序列:


    即两张牌,若花色不同,不论面值怎样,花色低的那张牌小于花色高的,只有在同花色情况下,大小关系才由面值的大小确定。这就是多关键码排序。

    为得到排序结果,我们讨论两种排序方法。
    方法1:先对花色排序,将其分为4 个组,即梅花组、方块组、红心组、黑心组。再对每个组分别按面值进行排序,最后,将4 个组连接起来即可。
    方法2:先按13 个面值给出13 个编号组(2 号,3 号,...,A 号),将牌按面值依次放入对应的编号组,分成13 堆。再按花色给出4 个编号组(梅花、方块、红心、黑心),将2号组中牌取出分别放入对应花色组,再将3 号组中牌取出分别放入对应花色组,……,这样,4 个花色组中均按面值有序,然后,将4 个花色组依次连接起来即可。

    设n 个元素的待排序列包含d 个关键码{k1,k2,…,kd},则称序列对关键码{k1,k2,…,kd}有序是指:对于序列中任两个记录r[i]和r[j](1≤i≤j≤n)都满足下列有序关系:

                                                                   

    其中k1 称为最主位关键码,kd 称为最次位关键码     。

     

    两种多关键码排序方法:

    多关键码排序按照从最主位关键码到最次位关键码或从最次位到最主位关键码的顺序逐次排序,分两种方法:

    最高位优先(Most Significant Digit first)法,简称MSD 法

    1)先按k1 排序分组,将序列分成若干子序列,同一组序列的记录中,关键码k1 相等。

    2)再对各组按k2 排序分成子组,之后,对后面的关键码继续这样的排序分组,直到按最次位关键码kd 对各子组排序后。

    3)再将各组连接起来,便得到一个有序序列。扑克牌按花色、面值排序中介绍的方法一即是MSD 法。

    最低位优先(Least Significant Digit first)法,简称LSD 法

    1) 先从kd 开始排序,再对kd-1进行排序,依次重复,直到按k1排序分组分成最小的子序列后。

    2) 最后将各个子序列连接起来,便可得到一个有序的序列, 扑克牌按花色、面值排序中介绍的方法二即是LSD 法。

     

    基于LSD方法的链式基数排序的基本思想

      “多关键字排序”的思想实现“单关键字排序”。对数字型或字符型的单关键字,可以看作由多个数位或多个字符构成的多关键字,此时可以采用“分配-收集”的方法进行排序,这一过程称作基数排序法,其中每个数字或字符可能的取值个数称为基数。比如,扑克牌的花色基数为4,面值基数为13。在整理扑克牌时,既可以先按花色整理,也可以先按面值整理。按花色整理时,先按红、黑、方、花的顺序分成4摞(分配),再按此顺序再叠放在一起(收集),然后按面值的顺序分成13摞(分配),再按此顺序叠放在一起(收集),如此进行二次分配和收集即可将扑克牌排列有序。   

    基数排序:

    是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以是稳定的。

    算法实现:

    [cpp] view plain copy

    1. Void RadixSort(Node L[],length,maxradix)  
    2. {  
    3.    int m,n,k,lsp;  
    4.    k=1;m=1;  
    5.    int temp[10][length-1];  
    6.    Empty(temp); //清空临时空间  
    7.    while(k<maxradix) //遍历所有关键字  
    8.    {  
    9.      for(int i=0;i<length;i++) //分配过程  
    10.     {  
    11.        if(L[i]<m)  
    12.           Temp[0][n]=L[i];  
    13.        else  
    14.           Lsp=(L[i]/m)%10; //确定关键字  
    15.        Temp[lsp][n]=L[i];  
    16.        n++;  
    17.    }  
    18.    CollectElement(L,Temp); //收集  
    19.    n=0;  
    20.    m=m*10;  
    21.   k++;  
    22.  }  
    23. }  

     

     

     

     

     

     

     

     

    总结

    各种排序的稳定性,时间复杂度和空间复杂度总结:

     我们比较时间复杂度函数的情况:

     

                                 时间复杂度函数O(n)的增长情况

    所以对n较大的排序记录。一般的选择都是时间复杂度为O(nlog2n)的排序方法。

     

    时间复杂度来说:

    (1)平方阶(O(n2))排序
      各类简单排序:直接插入、直接选择和冒泡排序;
     (2)线性对数阶(O(nlog2n))排序
      快速排序、堆排序和归并排序;
     (3)O(n1+§))排序,§是介于0和1之间的常数。

           希尔排序
    (4)线性阶(O(n))排序
      基数排序,此外还有桶、箱排序。

    说明:

    当原表有序或基本有序时,直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数,时间复杂度可降至O(n);

    而快速排序则相反,当原表基本有序时,将蜕化为冒泡排序,时间复杂度提高为O(n2);

    原表是否有序,对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

     

    稳定性:

    排序算法的稳定性:若待排序的序列中,存在多个具有相同关键字的记录,经过排序, 这些记录的相对次序保持不变,则称该算法是稳定的;若经排序后,记录的相对 次序发生了改变,则称该算法是不稳定的。 
         稳定性的好处:排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。另外,如果排序算法稳定,可以避免多余的比较;

    稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序

    不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序

     

    选择排序算法准则:

    每种排序算法都各有优缺点。因此,在实用时需根据不同情况适当选用,甚至可以将多种方法结合起来使用。

    选择排序算法的依据

    影响排序的因素有很多,平均时间复杂度低的算法并不一定就是最优的。相反,有时平均时间复杂度高的算法可能更适合某些特殊情况。同时,选择算法时还得考虑它的可读性,以利于软件的维护。一般而言,需要考虑的因素有以下四点:

    1.待排序的记录数目n的大小;

    2.记录本身数据量的大小,也就是记录中除关键字外的其他信息量的大小;

    3.关键字的结构及其分布情况;

    4.对排序稳定性的要求。

    设待排序元素的个数为n.

    1)当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序、堆排序或归并排序序。

       快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;
           堆排序 :  如果内存空间允许且要求稳定性的,

           归并排序:它有一定数量的数据移动,所以我们可能过与插入排序组合,先获得一定长度的序列,然后再合并,在效率上将有所提高。

    2)  当n较大,内存空间允许,且要求稳定性 =》归并排序

    3)当n较小,可采用直接插入或直接选择排序。

        直接插入排序:当元素分布有序,直接插入排序将大大减少比较次数和移动记录的次数。

        直接选择排序 :元素分布有序,如果不要求稳定性,选择直接选择排序

    5)一般不使用或不直接使用传统的冒泡排序。

    6)基数排序
    它是一种稳定的排序算法,但有一定的局限性:
      1、关键字可分解。
      2、记录的关键字位数较少,如果密集更好
      3、如果是数字时,最好是无符号的,否则将增加相应的映射复杂度,可先将其正负分开排序。

     

    原文链接:http://blog.csdn.net/hguisu/article/details/7776068

    展开全文
  • 0、排序算法说明 0.1 排序的定义 对一序列对象根据某个关键字进行排序。 0.2 术语说明 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面; 不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b...
  • 常用的八大排序算法图文详解

    千次阅读 2018-05-29 19:58:08
    概述排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。我们这里说说八大排序就是内部排序。 当n较大,则应...
  • 几种经典的排序算法

    千次阅读 2018-05-31 16:08:14
    1.冒泡排序 时间复杂度:O(n²) 冒泡排序算法的运作如下:(从后往前) 1)比较相邻的元素。如果第一个比第二个大,就交换他们两个。 2)对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点...
  • 几种常见的内部排序

    千次阅读 2018-01-06 21:53:23
    排序是计算机程序设计中的一种重要操作,它的功能是将一个数据元素的任意序列,重新排列成一个按关键字有序的序列。 排序分为内部排序和外部排序。 随着计算机的内存不断扩大和查找算法的不断优化,外部排序用到...
  • 十大经典排序算法

    千次阅读 多人点赞 2018-05-29 12:17:07
    十大经典排序算法(附有动图演示哦) A&gt;交换排序---冒泡排序 a&gt;冒泡排序(Bubble Sort) 算法描述:比较两个相邻的元素,如果升序的话,前面的比后面的大,就交换,这样一轮下来,就会找到这组数据中最大的...
  • 10大经典排序算法动画解析-收藏

    万次阅读 多人点赞 2019-12-22 14:20:20
    人工智能,零基础入门!... 排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序...常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序...
  • pandas 根据某一列排序(sort_values)

    万次阅读 2018-04-05 10:19:49
    pandas 根据某一列排序 pandas排序的方法有很多,sort_values表示根据某一列排序 pd.sort_values("xxx",inplace=True) 表示pd按照xxx这个字段排序,inplace默认为False,如果该值为False,那么原来的pd...
  • MongoDB中的排序规则

    万次阅读 2020-06-01 19:21:02
    $min $max类型不一样时会按照如下的类型判断大小值 最小 Null Number (ints , longs , doubles , decimals) Symbol , String Object Array BinData ObjectId Boolean Date ...最大 Regular Expression
  • LINUX的文件按时间排序

    万次阅读 2014-12-29 00:49:28
    > ls -alt # 按修改时间排序 > ls --sort=time -la # 等价于> ls -alt > ls -alc # 按创建时间排序 > ls -alu # 按访问时间排序   # 以上均可使用-r实现逆序排序 > ls -alrt # 按修改时间排序 ...
  • linux命令ll 按时间和大小排序显示

    万次阅读 2016-12-30 15:20:14
    ll不是命令,是ls -l的别名 按大小排序 [root@localhost ~]# ll -Sh  按时间排序 [root@localhost ~]# ll -rt ll -t 是降序, ll -t | tac 是升序
  • 十大经典排序算法动画演示

    万次阅读 多人点赞 2020-08-03 23:35:14
    AlgorithmMan by Iori V1.1概述1、冒泡排序2、快速排序3、直接插入排序4、选择排序5、归并排序6、堆排序7、希尔排序8、计数排序9、基数排序10、桶排序11、二叉树排序结语 概述 我从2018年08月05日开始陆续在CSDN...
  • pandas Dataframe按指定列值排序问题

    万次阅读 2019-05-08 08:51:43
    想查看按某列值排序后的情况,借鉴网上的解决办法: df.sort_values(by="sales" , ascending=False) by 指定列 ascending 想显示结果的话,可以将结果赋给另一个变量 b=df.sort_values(by="sales" , ascending=...
  • SQL实现分组排序和组内排序

    万次阅读 2017-05-01 09:58:11
    在对表做排序时,经常会遇到需要先按某一个列排序,再按这个列分组的统计值来对子组或者说其它列排序的需求,下面是一个典型案例实现的技术路径:利用Mysql find_in_set group_concatselect * from user order by ...
  • layui表格(table)排序

    万次阅读 2018-07-10 13:36:36
    layui表格本身提供sort排序,但是只能排序当前一页;如果后台返回几十页数据,需要排序显示,该如何做呢,这里闲心大神提供了一个sort监听方法:通过监听排序的列,把对应的参数传给后台,然后重渲染表格就行了 //...
  • top命令按内存和cpu排序

    万次阅读 2016-10-08 21:51:03
    一、按进程的CPU使用率排序 运行top命令后,键入大写P。 有两种途径: a) 打开大写键盘的情况下,直接按P键 b) 未打开大写键盘的情况下,Shift+P键 效果如图: 二、按进程的内存使用率排序 运行top命令后,...
  • 选择排序

    万次阅读 2018-07-19 18:26:21
    选择排序也是一种简单直观的排序算法。它的工作原理很容易理解:初始时在序列中找到最小(大)元素,放到序列的起始位置作为已排序序列;然后,再从剩余未排序元素中继续寻找最小(大)元素,放到已排序序列的末尾。...
1 2 3 4 5 ... 20
收藏数 2,043,463
精华内容 817,385
关键字:

排序