排序算法_排序算法整理 - CSDN
排序算法 订阅
所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范,要得到一个符合实际的优秀算法,得经过大量的推理和分析。 展开全文
所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。排序算法,就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范,要得到一个符合实际的优秀算法,得经过大量的推理和分析。
信息
优    点
节省时间,简化计算
外文名
Sorting algorithm
分    类
计算机算法
应用语言
c++等
中文名
排序算法
排序算法概述
所谓排序算法,即通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。这种新序列遵循着一定的规则,体现出一定的规律,因此,经处理后的数据便于筛选和计算,大大提高了计算效率。对于排序,我们首先要求其具有一定的稳定性,即当两个相同的元素同时出现于某个序列之中,则经过一定的排序算法之后,两者在排序前后的相对位置不发生变化。换言之,即便是两个完全相同的元素,它们在排序过程中也是各有区别的,不允许混淆不清。 [1] 
收起全文
精华内容
参与话题
  • 冒泡排序算法

    2019-10-29 14:36:08
    掌握常用的查找算法 掌握常用的排序算法 掌握常用的树算法 提高面试竞争力
  • 八大排序算法

    万次阅读 多人点赞 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

     

     

     

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

             

    展开全文
  • 十大经典排序算法

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

    十大经典排序算法(附有动图演示哦吐舌头)

          


    A>交换排序---冒泡排序

      a>冒泡排序(Bubble Sort)

     算法描述:比较两个相邻的元素,如果升序的话,前面的比后面的大,就交换,这样一轮下来,就会找到这组数据中最大的元素,然后抛开这个元素继续重复上述步骤.知道排完为止.   

       b>冒泡排序(Bubble Sort)动图演示


    b>冒泡排序(Bubble Sort)代码实现

    #include<stdio.h>
    #include<stdlib.h>
    void swap(int *a, int *b){
    	int ret = 0;
    	ret = *a;
    	*a = *b;
    	*b = ret;
    }
    void Bubble_sort(int *arr,int size){
    	int i = 0;
    	int j = 0;
    	for ( i = 0; i < size-1; i++)
    	{
    		for (j = 0; j < size-1-i; j++)
    		{
    			if (arr[j]>arr[j+1])//这是升序的写法,降序将改为if(arr[j]<arr[j+1])
    			{
    				swap(&arr[j], &arr[j+1]);
    			}
    		}
    	}
    }
    int main(){
    	int i = 0;
    	int arr[10] = { 2, 0, 4, 9, 3, 6, 8, 7, 1, 5 };
    	int size = sizeof(arr) / sizeof(arr[0]);
    	Bubble_sort(arr,size);
    	for ( i = 0; i < size; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	system("pause");
    	return 0;
    }

    A>交换排序---快速排序

       a>快速排序(Quick Sort)

         算法描述:任取待排序中的某一元素作为基准值,按照该排序码,将待排序集合分割成两个子序列,左边的序列比基准值小,右边的比基准值大.然后对左右子序列重复上述步骤.直到排完为止

       b>快速排序(Quick Sort)动图展示


       c>快速排序代码实现(Quick Sort)

    #include "stack.h"
    #include<stdio.h>
    #include<stdlib.h>
    void swap(int *a, int *b){
    	int ret = 0;
    	ret = *a;
    	*a = *b;
    	*b = ret;
    }
    //设定一个基准值,在保证不越界的情况下,从前往后查找比基准值小的元素,找到了然后停下来,若begin和end没有相遇,就交换,相遇了
    //就交换begin和数组中基准值所代表的元素
    int GetBaseKey(int *array,int left,int right){
    	int mid = left + ((right - left) >> 1);
    	if (array[left]<array[right]){
    		if (array[mid]<array[left])
    			return left;
    		else if (array[mid]>array[right])
                return right;
    	    else
    	        return mid;
    		
    	}
    	else
    	{
    		if (array[mid]>array[left])
    		   return left;
    	    else if (array[mid] < array[right])
    		   return right;
    		else
    			return mid;
    	}
    }
    //Hoare版本
    int partion_hoare(int *array, int left, int right){
    	int begin = left;
    	int end = right - 1;
    	int key_index = GetBaseKey(array, left, right-1);
    	swap(&array[key_index], &array[right - 1]);
    	int key = array[right-1];
    	while (begin<end)
    	{
    		while ((begin<end)&&array[begin]<key)
    		   begin++;
    		while ((begin<end)&&array[end]>=key)
    		   end--;
    		if (begin<end)
    		   swap(&array[begin], &array[end]);
    		
    	}
    	if (begin!=right-1)
    	   swap(&array[begin], &array[right-1]);
    	return begin;
    }
    //快速排序---挖坑法
    int partion_WK(int *array, int left, int right){
    	int begin = left;
    	int end = right-1;
    	int key_index = GetBaseKey(array, left, right - 1);
    	swap(&array[key_index], &array[right - 1]);
    	int key = array[right - 1];
    	while (begin<end)
    	{
    		while (begin<end&&array[begin]<key)
    		  begin++;
    		if (begin < end)
    		{
    			array[end] = array[begin];
    			end--;
    		}
    		while (begin<end&&array[end]>key)
    			end--;
    		if (begin < end)
    		{
    			array[begin] = array[end];
    			begin++;
    		}
    	}
    	if (begin!=right-1)
    	{
    		array[begin] = key;
    	}
    	return begin;
    }
    //快速排序---前后指针
    int partion_P(int *array, int left, int right){
    	int pre = left-1;
    	int pcur = left;
    	int key_index = GetBaseKey(array, left, right - 1);
    	swap(&array[key_index], &array[right - 1]);
    	int key = array[right - 1];
    	while (pcur<right)
    	{
    		if (array[pcur] < key&&(++pre) != pcur)
    			swap(&array[pre], &array[pcur]);
    		pcur++;
    		
    	}
    	if ((++pre)!=right-1)
    	{
    		swap(&array[pre], &array[right-1]);
    	}
    	return pre;
    }
    //递归
    void QuickSort(int *array,int left,int right){
    	if (right-left>1)
    	{
    		//int base = partion_hoare(array, left, right);
            //int base = partion_WK(array, left, right);
    		int base = partion_P(array, left, right);
    		QuickSort(array, 0, base);
    		QuickSort(array,base+1,right);
    	}
    }
    //非递归,利用栈保存边界
    int QuickSort_Nor(int *array,int size){
    	int base = 0;
    	int left = 0;
    	int right = 0;
    	SeqStack s;
    	StackInit(&s);
    	StackPush(&s,size);//保存右边界
    	StackPush(&s, 0);//保存左边界
    	while (!StackEmpty(&s))
    	{
    		left = StackTop(&s);
    		StackPop(&s);
    		right = StackTop(&s);
    		StackPop(&s);
    		if (left<right)
    		{
    			base = partion_hoare(array, left, right);
    			StackPush(&s, right);//保存右边界
    			StackPush(&s, base + 1);//保存左边界
    			StackPush(&s, base);
    			StackPush(&s, left);
    		}
    		
    	}
    	
    }
    int main(){
    	int i = 0;
    	int arr[] = {2,0,4,9,3,6,8,7,1,5};
    	//int arr[] = {1,2,3,4,5,6};
    	int size = sizeof(arr) / sizeof(arr[0]);
    	//QuickSort(arr,0,size);
    	QuickSort_Nor(arr, size);
    	for (i = 0; i < size; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	printf("\n");
    	system("pause");
    	return 0;
    }
    

    B>插入排序---直接插入排序

       a>直接插入排序(Insertion sort)

      算法描述:从第一个元素开始,该元素已经排好序,继续取元素与排好序的元素依次进行比较,升序的话插入到比前一个大比后一个小的位置,然后重复上述步骤,直到插完元素为止.

      b>直接插入排序(Insertion sort)动图展示


      c>直接插入排序(Insertion sort)代码实现

    #include<stdio.h>
    #include<stdlib.h>
    //二分查找相比较顺序查找而言,比较的次数比较少.
    //插入排序在原本升序排升序,原本逆序排逆序,元素集合接近有序时,直接插入排序效率较高.
    //直接插入排序,顺序查找
    void insert_sort(int *pArr, int size){
    	int i = 0;
    	int key = 0;
    	int end = 0;
    	for ( i = 1; i < size; i++)
    	{
    		key = pArr[i];
    		end = i - 1;
    		while (end>=0&&key<pArr[end])
    		{
    			pArr[end+1]=pArr[end];
    			end--;
    		}
    		pArr[end + 1] = key;
    	}
    }
    //直接插入排序,二分查找
    void insert_sort_second(int *pArr, int size){
    	int left = 0;
    	int right = size-1;
    	int mid = 0;
    	int i = 0;
    	int key = 0;
    	for (i = 1; i < size; i++)
    	{
    		key = pArr[i];
    		left = 0;
    		right = i - 1;
    		//二分查找寻找待插入元素的位置
    		while (left <= right)
    		{
    			mid = (left + right) >> 1;
    			if (key<pArr[mid])
    			{
    				right = mid - 1;
    			}
    			else
    			{
    				left = mid + 1;
    			}
    		}
    		//搬移left位置以后的元素
    		right = i - 1;
    		while (right>=left)
    		{
    			pArr[right + 1] = pArr[right];
    			right--;
    		}
    		//插入元素
    		pArr[left] = key;
        }
    }
    int main(){
    	int i = 0;
    	int array[9] = {2,6,4,9,5,8,7,0,1};
    	int size = sizeof(array) / sizeof(array[0]);
    	//insert_sort(array, size);
    	insert_sort_second(array, size);
    	for ( i = 0; i < size; i++)
    	{
    		printf("%d ", array[i]);
    	}
    	printf("\n");
    	system("pause");
    	return 0;
    }

    B>插入排序---希尔排序(直接插入排序的优化)

        a>希尔排序(Shell sort)     

       算法描述:对整个待排序序列进行分组,然后对每一组进行直接插入排序.

                                     

      b>希尔排序(Shell sort)动图展示


    c>希尔排序(Shell sort)代码实现

    #include<stdio.h>
    #include<stdlib.h>
    void Shell_Sort(int *pArr,int size){
    	int i = 0;
    	int key = 0;
    	int end = 0;
    	int gap = 3;
    	while (gap > 0)
    	{
    		for (i = gap; i < size; i++)
    		{
    			key = pArr[i];
    			end = i - gap;
    			while (end >= 0 && key<pArr[end])
    			{
    				pArr[end + gap] = pArr[end];
    				end=end-gap;
    			}
    			pArr[end + gap] = key;
    		}
    		gap--;
    	}
    }
    int main(){
    	int i = 0;
    	int array[9] = { 2, 6, 4, 9, 5, 8, 7, 0, 1 };
    	int size = sizeof(array) / sizeof(array[0]);
    	Shell_Sort(array, size);
    	for (i = 0; i < size; i++)
    	{
    		printf("%d ", array[i]);
    	}
    	printf("\n");
    	system("pause");
    	return 0;
    }

    C>选择排序---直接选择排序   

    a>直接选择排序(Insertion sort)

       算法描述:在未排序的序列中找到最小的元素,存放到序列的首位置,找到最大的元素存放到序列的末尾.然后抛开首位和末尾,继续重复该步骤,直到排完为止.

     b>直接选择排序(Insertion sort)动图展示


     c>直接选择排序(Insertion sort)代码实现

    #include<stdio.h>
    #include<stdlib.h>
    void swap(int *a,int *b){
    	int ret = 0;
    	ret = *a;
    	*a = *b;
    	*b = ret;
    }
    void Selection(int *arr,int size){
    	int left = 0;
    	int right = size - 1;
    	int i = 0;
    	while (left<right)
    	{
    		int MinIndex = left;
    		int MaxIndex = left;
    		for (i = left; i <= right; i++)
    		{
    			if (arr[MinIndex]>arr[i])
    				MinIndex = i;
    			if (arr[MaxIndex]<arr[i])
    				MaxIndex = i;
    		}
    		swap(&arr[left],&arr[MinIndex]);
    		if (MaxIndex==left)
    		{
    			MaxIndex = MinIndex;
    		}
    		swap(&arr[right], &arr[MaxIndex]);
    		left++;
    		right--;
    	}
    }
    int main(){
    	int i = 0;
    	int arr[10] = {2,5,4,9,3,6,8,7,1,0};
    	int size = sizeof(arr) / sizeof(arr[0]);
    	Selection(arr,size);
    	for ( i = 0; i < size; i++)
    	{
    		printf("%d ",arr[i]);
    	}
    	system("pause");
    	return 0;
    }
    C>选择排序---堆排序   

    a>堆排序(Heap sort)

       算法描述:若升序的话,就将堆调成一个大堆,若降序的话,就将堆调成一个小堆.从倒数第一个非叶子节点开始往根遍历,若当前节点的值都大于左右孩子,则不用动,若是小于,就将左右孩子当中最大的节点与当前节点交换,交换后就需要进行向下调整(因为交换会影响大堆结构).重复上述步骤,直到根节点为止.

      b>堆排序(Heap sort)动图展示


      c>堆排序(Heap sort)代码实现

    #include "Heap.h"
    #include<stdio.h>
    #include<stdlib.h>
    //向下调整 
    void HeapAdjust(int *arrar,int size,int parent){
    	int child = parent * 2 + 1;
    	while (child<size)
    	{
    		if ((child + 1)<size&&arrar[child + 1]>arrar[child])
    			child += 1;
    		if (arrar[parent]<arrar[child])
    		{
    			swap(&arrar[parent], &arrar[child]);
    			parent = child;
    			child = parent * 2 + 1;
    		}
    		else
    		  return;
    	
    	}
    	
    }
    void HeapSort(int arrar[],int size){
    	//1,建堆
    	int root = ((size - 2) >> 1);
    	int end = size - 1;
    	for ( ;  root>=0; --root)
    	{
    		HeapAdjust(arrar, size, root);
    	}
    	//2,调整
    	while (end)
    	{
    		swap(&arrar[end],&arrar[0]);
    		HeapAdjust(arrar, end, 0);
            --end;
    	}
    
    }
    int main(){
    	int arrar[] = { 53, 17, 78, 9, 45, 65, 87, 23, 31 };
    	int size = sizeof(arrar) / sizeof(arrar[0]);
    	HeapSort(arrar,size);
    	for (int i = 0; i <size; i++)
    	{
    		printf("%d ", arrar[i]);
    	}
    	system("pause");
    	return 0;
    }

    D>归并排序(Merge Sort)   

       a>归并排序(Merge Sort)      

      算法描述:将待排序的元素序列分为两个长度相等的子序列,对每个子序列进行排序,然后将他们合并成一个序列,合并两个子序列的过程称为二路归并.

       b>归并排序(Merge Sort)动图展示     


      c>归并排序(Merge Sort)代码演示

    #include<stdio.h>
    #include<stdlib.h>
    #include<malloc.h>
    #include<string.h>
    #include<assert.h>
    //归并
    void MergeData(int *arr,int left,int mid,int right,int *temp){
    	int temp_index = left;
    	int left_L = left;
    	int left_R = mid;
    	int right_L = mid;
    	int right_R = right;
    	while (left_L<left_R && right_L<right_R)
    	{
    		if (arr[left_L]<arr[right_L])
    		{
    			temp[temp_index++] = arr[left_L++];
    
    		}
    		else
    		{
    			temp[temp_index++] = arr[right_L++];
    		}
    
    	}
    	while(left_L<left_R)
    	{
    		temp[temp_index++] = arr[left_L++];
    	}
    	while (right_L<right_R)
    	{
    		temp[temp_index++] = arr[right_L++];
    	}
    
    }
    //分组
    //void *memcpy(void*dest, const void *src, size_t n);
    //由src指向地址为起始地址的连续n个字节的数据复制到以dest指向地址为起始地址的空间内。
    void _MergeSort(int *arr, int left, int right, int *temp){
    	if ((right-left)>1)
    	{
    		int mid = left + ((right-left)>>1);
    		_MergeSort(arr,left,mid,temp);
    		_MergeSort(arr, mid, right, temp);
    		MergeData(arr,left,mid,right,temp);
    		memcpy(arr+left,temp+left,sizeof(int)*(right-left));
    	}
    
    
    }
    //递归
    void MergeSort(int *arr,int size){
    	int *temp = (int *)malloc(size*sizeof(arr[0]));
    	if (temp==NULL)
    	{
    		assert(0);
    		return;
    	}
    	_MergeSort(arr,0,size,temp);
    	free(temp);
    }
    //非递归
    void MergeSort_Nor(int *arr, int size){
    	int *temp = (int *)malloc(size*sizeof(arr[0]));
    	if (temp == NULL)
    	{
    		assert(0);
    		return;
    	}
    	int i = 0;
    	int gap = 1;
    	while (gap<size)
    	{
    		for (i = 0; i < size;i+=2*gap){
    			int left = i;
    			int mid = left + gap;
    			int right = mid + gap;
    			if (mid>size)
    			{
    				mid = size;
    			}
    			if (right>size)
    			{
    				right = size;
    			}
    			MergeData(arr, left, mid, right, temp);
    		}
    		memcpy(arr,temp,size*sizeof(arr[0]));
    		gap=gap*2;
    	}
    	free(temp);
    }
    int main(){
    	int arr[10] = { 2, 0, 4, 9, 3, 6, 8, 7, 1, 5 };
    	int size = sizeof(arr) / sizeof(arr[0]);
    	MergeSort(arr,size);
    	//MergeSort_Nor(arr, size);
    	for (int i = 0; i < size; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	system("pause");
    	return 0;
    }

    E>计数排序(鸽巢原理)(Counting Sort)   

       a>计数排序(Counting Sort)        

      算法描述:找到待排序列中最大最小的元素,然后以此确定临时空间的大小,在临时空间中,以待排序列组中元素的大小为下标,该元素出现的次数为该下标对应的元素,根据临时空间的统计结果,重新对元素进行回收.

       b>计数排序(Counting Sort)动图展示     


      c>计数排序(Counting Sort)代码实例

    #include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    #include<string.h>
    #include<malloc.h>
    int GetMaxValue(int *arr,int size){
    	int i = 0;
    	int max = arr[0];
    	for ( i = 1; i < size; i++)
    	{
    		if (arr[i]>max)
    			max = arr[i];
    	}
    	return max;
    
    }
    int GetMinValue(int *arr, int size){
    	int i = 0;
    	int min = arr[0];
    	for (i = 1; i < size; i++)
    	{
    		if (arr[i]<min)
    			min = arr[i];
    	}
    	return min;
    
    }
    void _Count_Sort(int *arr, int *temp,int size,int ret,int min){
    	int i = 0;
    	int index = 0;
    	//统计个数
    	for ( i = 0; i < size; i++)
    	{
    		temp[arr[i]-min]++;
    	}
    	//回收,把temp里的数据回收到原空间里
    	for ( i = 0; i <ret ; i++)
    	{
    		while (temp[i]--)
    		{
    			arr[index++] = i+min;
    		}
    	}
    	free(temp);
    }
    void Count_Sort(int *arr,int size){
    	int max = GetMaxValue(arr,size);
    	int min = GetMinValue(arr, size);
    	int ret = max - min + 1;
    	int *temp = (int *)malloc(ret*sizeof(arr[0]));
    	if (temp==NULL)
    	{
    		assert(0);
    		return;
    	}
    	//memset作用是在一段内存块中填充某个给定的值,它是对较大的结构体或数组进行清零操作的一种最快方法
    	memset(temp,0,ret*sizeof(int));
        _Count_Sort(arr,temp,size,ret,min);
    }
    int main(){
    	int i = 0;
    	int arr[10] = {3,4,3,2,1,2,6,5,4,7};
    	int size = sizeof(arr) / sizeof(arr[0]);
        Count_Sort(arr,size);
    	for ( i = 0; i < size; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	system("pause");
    	return 0;
    }
    F>基数排序(Radix Sort)----LSD(底关键码)

       a>基数排序(Radix Sort)    

      算法描述:把待排序中的元素按照低位先排序,然后收集,再按照高位排序,再收集,直至最高位.①,获取序列中的最大数,然后取得其位数,然后利用计数排序的特点,定义10个元素的数组,分别统计以待排序列元素的每一位为数组的下标的元素的个数,然后再定义一个数组存每个的起始地址.开一个辅助空间,放置元素.再回收这些元素.

     b>基数排序(Radix Sort)动图展示

     c>基数排序(Radix Sort)代码展示


    #include<stdio.h>
    #include<stdlib.h>
    #include<assert.h>
    #include<malloc.h>
    #include<string.h>
    //统计最大元素的位数
    int GetMaxValue_BitCount(int *arr,int size){
    	int i = 0;
    	int count = 1;
    	int ret = 10;
    	for ( i = 0; i < size; i++)
    	{
    		while (arr[i] >= ret)
    		{
    			count++;
    			ret *= 10;
    		}
    	}
    	return count;
    }
    void _RadixSort(int *arr,int size,int *temp){
    	int Max_BitCount = GetMaxValue_BitCount(arr, size);
    	//存每个桶中元素的个数.
    	int count[10] = { 0 };
    	//存每个桶的起始地址
    	int start_Addr[10] = { 0 };
    	int i = 0;
    	int ret = 1;
    	int index = 0;
    	while (Max_BitCount)
    	{
    		//统计个数
    		for ( i = 0; i < size; i++)
    		{
    			count[arr[i] / ret % 10]++;
    		}
    		//计算地址
    		for ( i = 1; i < 10; i++)
    		{
    			start_Addr[i] = start_Addr[i - 1] + count[i - 1];
    		}
    		//放置元素到临时空间中
    		for (i = 0; i <size; i++){
    			int Addr = arr[i]/ret% 10;
    			temp[start_Addr[Addr]++] = arr[i];
    		}
    		//回收元素
    		//memcpy函数的功能是从源src所指的内存地址的起始位置开始拷贝n个字节到目标dest所指的内存地址的起始位置中。
    		//void *memcpy(void *dest, const void *src, size_t n);
    		memcpy(arr,temp,size*sizeof(arr[0]));
    		ret *= 10;
    		Max_BitCount--;
    	}
    
    }
    void RadixSort(int *arr,int size){
    	int *temp = (int *)malloc(size*sizeof(arr[0]));
    	if (temp==NULL)
    	{
    		assert(0);
    		return;
    	}
    	_RadixSort(arr,size,temp);
    	free(temp);
    }
    int main(){
    	int arr[11] = {198,254,378,852,761,554,581,552,605,479,853};
    	int size = sizeof(arr) / sizeof(arr[0]);
    	RadixSort(arr,size);
    	for (int  i = 0; i < size; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	system("pause");
    	return 0;
    }


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

    万次阅读 多人点赞 2019-04-27 17:04:36
    最简单的一种排序算法。假设长度为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);
    	}
    }

     

    展开全文
  • 超详细的八大排序算法的各项比较以及各自的特点

    万次阅读 多人点赞 2018-08-09 23:01:56
    一、八大排序算法的总体比较 二、算法各自的特点(具体实现见后面博客) 1.快排 (1)算法思想 选择一个基准元素,将比基准元素小的元素放在其前面,比基准元素大的元素放在其后面,然后在将小于基准值元素的...

    一、八大排序算法的总体比较

    二、算法各自的特点(具体实现见后面博客)

    1.快排

    (1)算法思想

    选择一个基准元素,将比基准元素小的元素放在其前面,比基准元素大的元素放在其后面,然后在将小于基准值元素的子数列和大于基准元素的子数列按原来的方法排序,直到整个序列有序;

    (2)优缺点

    优点:极快数据移动少;

    缺点:不稳定;

    (3)效率分析

    此排序算法的效率在序列越乱的时候,效率越高。在数据有序时,会退化成冒泡排序;

    (4)对于基准的选择

    a.三数取中

    具体思想:对待排序序列中low、mid、high三个位置上数据进行排序,取他们中间的那个数据作为枢轴,并用0下标元素存储枢轴;

    b.随机选取基准

    引入原因:在待排序列是部分有序时,固定选取枢轴使快排效率低下;

    具体思想:取在待排序列中任意一个元素作为基准;

    (5)优化方法

    a.当待排序序列的长度分割到一定大小后,使用插入排序;

    原因:对于很小和部分有序的数组,快排不如插排好。当待排序序列的长度分割到一定大小后,继续分割的效率比插入排序要差,此时可以使用插排而不是快排;

    b.在一次分割结束后,可以把与key相等的元素聚集在一起,继续下次分割时,不必再对于key相等元素分割;

    (6)应用场景

     a.求数组中第k小的数

    将数组中某一个元素m作为划分依据,即m=arr[0]。若m前面的元素个数大于k,则第k小的数一定在m前面的元素中,这时我们只需要继续在m前面的元素中找第k小的数;若m前面的元素小于k,则第k小的数一定在m后面的元素中,这时我们只需要在m后面的元素中找第k小的数;

    2.冒泡排序

    (1)基本原理

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

    (2)优缺点

    优点:稳定

    缺点:慢,每次只能移动两个相邻的数据;

    3.插入排序

    (1)基本思想

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

    (2)优缺点

    优点:稳定,快

    缺点:比较次数不一定,比较次数越少,插入点后的数据移动越多,特别是数据量庞大的时候

    4.堆排序

    4.1、二叉堆定义:

    二叉堆是完全二叉树或近似完全二叉树。二叉堆满足两个特性:

    (1)父结点的键值总是大于或者等于(小于或者等于)任何一个子节点的键值;

    (2)每个结点的左子树和右子树都是一个二叉堆;

    当父结点的键值总是大于或者等于任何一个子节点的键值时为大根堆。当父结点的键值总是小于或等于任何一个子节点的键值时为小根堆;

    4.2、堆的存储:

    一般都用数组来表示堆,i结点的父结点下标就为(i-1)/2.它的左右子节点的下标分别为2*i+1和2*i+2.

    4.3、堆的插入:

    每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列,然后将这个新数据插入到这个有序数据中

    (1)用大根堆排序的基本思想

    先将初始数组建成一个大根堆,此对为初始的无序区;

    再将最大的元素和无序区的最后一个记录交换,由此得到新的无序区和有序区,且满足<=的值;

    由于交换后新的根可能违反堆性质,故将当前无序区调整为堆。然后再次将其中最大的元素和该区间的最后一个记录交换,由此得到新的无序区和有序区,且仍满足关系的值<=的值,同样要将其调整为堆;

    ..........

    直到无序区只有一个元素为止;

    4.4:应用

    寻找M个数中的前K个最小的数并保持有序;

    时间复杂度:O(K)[创建K个元素最大堆的时间复杂度] +(M-K)*log(K)[对剩余M-K个数据进行比较并每次对最大堆进行从新最大堆化]

    5.希尔排序

    (1)基本思想

    先将整个待排序元素序列分割成若干子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直接插入排序(因为直接插入排序在元素基本有序的情况下,效率很高);

    (2)适用场景

    比较在希尔排序中是最主要的操作,而不是交换。用已知最好的步长序列的希尔排序比直接插入排序要快,甚至在小数组中比快速排序和堆排序还快,但在涉及大量数据时希尔排序还是不如快排;

    6.归并排序

    (1)基本思想

    首先将初始序列的n个记录看成是n个有序的子序列,每个子序列的长度为1,然后两两归并,得到n/2个长度为2的有序子序列,在此基础上,再对长度为2的有序子序列进行两两归并,得到若干个长度为4的有序子序列,以此类推,直到得到一个长度为n的有序序列为止;

    (2)适用场景

    若n较大,并且要求排序稳定,则可以选择归并排序;

    7.简单选择排序

    (1)基本思想

    第一趟:从第一个记录开始,将后面n-1个记录进行比较,找到其中最小的记录和第一个记录进行交换;

    第二趟:从第二个记录开始,将后面n-2个记录进行比较,找到其中最小的记录和第2个记录进行交换;

    ...........

    第i趟:从第i个记录开始,将后面n-i个记录进行比较,找到其中最小的记录和第i个记录进行交换;

    以此类推,经过n-1趟比较,将n-1个记录排到位,剩下一个最大记录直接排在最后;

    8.交换排序

     

     

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

    万次阅读 多人点赞 2019-10-12 16:00:20
    排序算法可以说是一项基本功,解决实际问题中经常遇到,针对实际数据的特点选择合适的排序算法可以使程序获得更高的效率,有时候排序的稳定性还是实际问题中必须考虑的,这篇博客对常见的排序算法进行整理,包括:...
  • 常见的排序算法有哪些?如何实现这些算法?

    万次阅读 多人点赞 2018-08-07 22:10:31
    在计算机科学与数学中,排序算法(Sorting algorithm)是一种能将一串资料依照特定排序方式进行排列的一种算法。 最常用到的排序方式是数值顺序以及字典顺序。 有效的排序算法在一些算法(例如搜寻算法与合并算法)...
  • 常见十大(内部)排序算法 - Sorting Algorithms C++

    万次阅读 多人点赞 2018-09-16 11:11:36
    基本概念 内部和外部排序 内部排序在这里指的是只用到了电脑内存...难道有排序算法不需要比较吗?的确有,但是不多。常见的有三种:计数排序,桶排序,基数排序。它们用统计的方法规避了比较,详细的可查看之后讲...
  • 快速排序算法

    万次阅读 多人点赞 2019-03-06 20:52:40
    但是这种算法时间复杂度高,当需要排序的元素较多时,程序运行时间很长,因此产生了快速排序算法。该算法的实现可分为以下几步: 1. 在数组中选一个基准数(通常为数组第一个); 2. 将数组中小于基准数的数据移到...
  • 本文对常见排序算法进行总结。 排序算法 冒泡排序 该算法比较简单,几乎所有语言涉及到算法时,都会涉及到冒泡算法。 算法思路: 比较相邻的元素。如果第一个比第二个大,就交换他们两个。 对每一对...
  • 七种常见的VB排序算法示例程序

    千次阅读 2014-11-28 00:23:57
    七种常见的VB排序算法示例程序 加入了微秒级的计时器,各种不同算法的速度马上就能比较出来了,有的算法还真的是从没听说过,看也看不懂。 cmbSorts.AddItem "冒泡排序法" cmbSorts.AddItem "插入排序法" ...
  • 冒泡排序法

    万次阅读 多人点赞 2019-08-05 20:41:40
    冒泡排序法 冒泡排序法原理示意图 public static void ArraySortTest() { int[] ages= {21,27,31,19,50,32,16,25}; System.out.println(Arrays.toString(ages)); //控制比较轮数 for(int i=1;i<ages....
  • 算法】选择排序法

    万次阅读 2018-08-22 09:24:31
    1.选择排序法是将序列分为两段,有序前列和无序后列,每次查找无序后列中最大元素,将其插入到有序前列的最末尾处,直至无序后列最后一个元素,最终排序后的序列为降序序列 2.适用于包括数组和向量在内的序列 3....
  • 算法排序----插入排序法

    万次阅读 热门讨论 2018-06-02 18:59:50
    接下来我来讲述一下插入排序法。首先来解释一下插入排序法的原理,它的原理是每插入一个数都要将它和之前的已经完成排序的序列进行重新排序,也就是要找到新插入的数对应原序列中的位置。那么也就是说,每次插入一个...
  • 从vb的角度看几种简单的排序法

    万次阅读 热门讨论 2019-05-29 11:29:31
    老农看代码,比如老农看一亩地里的一棵苗,可以用哪一行,哪一列来形容,放在计算机里,即用i,j表示,然后老农所看到的...一、冒泡排序法(左为原理图,右为代码) 二、选择排序法(左为原理图,右为代...
  • c语言实现冒泡排序法

    万次阅读 2018-08-27 23:13:28
    冒泡排序是排序算法中较为简单的一种,英文称为Bubble Sort。它遍历所有的数据,每次对相邻元素进行两两比较,如果顺序和预先规定的顺序不一致,则进行位置交换;这样一次遍历会将最大或最小的数据上浮到顶端,之后...
  • 冒泡法排序算法(C语言实现)

    千次阅读 多人点赞 2018-03-19 15:21:01
    冒泡法排序demo
  • 冒泡排序算法代码

    万次阅读 2017-08-16 16:08:02
    冒泡排序算法代码
  • Java中的冒泡排序算法-简单实例

    万次阅读 多人点赞 2020-04-21 22:53:41
    冒泡算法的原理实现:(从小到大排序) 1:比较相邻的两个元素,如果第一个比第二个大就交换位置。 2:对每一对相邻的元素进行比较,从开始第一队到结尾的最后一对,这样最后的元素就是最大的了。 3:每一次...
1 2 3 4 5 ... 20
收藏数 783,690
精华内容 313,476
关键字:

排序算法