精华内容
下载资源
问答
  • 直接选择排序 直接选择排序 :在未排序的元素中选出最小的元素,然后和未排序的首元素进行交换 ,直到所有元素 排序完成 。...//设置一个函数,将尺寸为size的数组a[]中的元素按照大小排列 int..

    直接选择排序

    直接选择排序 :在未排序的元素中选出最小的元素,然后和未排序的首元素进行交换 ,直到所有元素 排序完成 。

    #include <iostream>
    #include <iomanip>
    using namespace std;
    void sort(int a[],int size) ;//设置一个函数,将尺寸为size的数组a[]中的元素按照大小排列
    int main()
    {
    	int b[]={3,5,2,1,7,9,6};
    	int size=sizeof(b)/sizeof(int);
    	sort( b, size);//不要带数据类型 
    	cout<<"输出排列后的数组元素"<<endl;
    	for (int i=0;i<size;i++)
    	{
    		cout<<setw(2)<<b[i];
    	}
    	return 0;
     } 
     void sort(int a[],int size)
     {
     	cout<<"输出排列之前的数组元素"<<endl;
    	 for(int i=0;i<size;i++)
    	 {
    	 	cout<<setw(2)<<a[i];
    	  } 
    	for(int j=0;j<size;j++)
    	{
    		int min=a[j],mink=j;
    		for(int k=j;k<size;k++)
    	/*把除参考值以外的值跟参考值比一下,重新定位第一个最小值,然后再把剩下的值和第一个最小值比一下,最终定位到真正意义上的最小值,然后把最终的最小值和参考值的位置调换一下,此内循环结束,然后再改大条件j*/ 
    		{
    			if(a[k]<min)
    			{
    				min=a[k];
    				mink=k;
    			}
    		}
    	int temp=a[j];//感觉自己像一个白痴,这不是把a[j]值和a[mink]值进行交换嘛!!
    	a[j]=a[mink];
    	a[mink]=temp;
    	}
    	cout <<endl;
    	
     }
    

    快速排序法

    #include<iostream>  
        using namespace std;  
        void quickSort(int a[],int,int);  
        int main()  
        {  
            int array[]={34,65,12,43,67,5,78,10,3,70},k;  
            int len=sizeof(array)/sizeof(int);  
            cout<<"The orginal arrayare:"<<endl;  
            for(k=0;k<len;k++)  
                cout<<array[k]<<",";  
            cout<<endl;  
            quickSort(array,0,len-1);  
            cout<<"The sorted arrayare:"<<endl;  
            for(k=0;k<len;k++)  
                cout<<array[k]<<",";  
            cout<<endl;  
            system("pause");  
            return 0;  
        }  
          
        void quickSort(int s[], int l, int r)  
        {  
            if (l< r)  //这是大前提,若数组里就一个元素就都不执行了
            {        
                int i = l, j = r, x = s[l];  //一般i=0;j=size-1
                while (i < j)  
                {  
                    while(i < j && s[j]>= x)         
                       j--;   
        /*从右向左找第一个小于x的数 ,如果循环语句只有一句,大括号可以省略,直到不满足循环条件再继续运行下一句*/
                    if(i < j)  
                        s[i++] = s[j];
    /*终于搞懂了!!i++是先用i用完再把i+1,先把s[j]值赋值给s[i],运行完i再加1(因为下一个从左到右寻找最大值就要从i+1位开始寻找了)语句可以拆分为s[i] = s[j];i++; */
                    while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数  
                        i++;   
                    if(i < j)  
                        s[j--] = s[i];  
                }  
                s[i] = x;  
                quickSort(s, l, i - 1); // 递归调用  
                quickSort(s, i + 1, r);  
            }  
        }  
    

    思路:(1)首先选择数组其中y位作为索引记为K,这样这一位的值被暂存到X内,然后array[y]就变成空位了。
    (2)记i=left,j=right,一般j是最后一位,运行此步骤要保证数组元素要大于2个,即i<j,然后从最后一位寻找比索引小的值,然后把此位置上的值放在a[y]位,然后这个位置就空了,然后再从最左边一位寻找比索引值大的值放在空的那里,就这样进行迭代,直到i=j。
    (3)经过第二步,左边都是小于索引值,右边都是大于索引值,然后将左边再变成下一个区间,重复第一步和第二步。右边也同理。就这样重复调用函数,直到区间里就剩一个元素了即i=j那么顺序就排好了。

    插叙排序法

    思路:整个序列分为有序区和无序区,取第一个元素作为初始有序区,然后第二个开始,依次插入到有序区的合适位置,直到排好序。

    void InsertSort(int arr[],int n)
    {
        for (int i =1;i <= n;++i)
        {
            for(int j = i;j > 0;--j)
            {
                if(arr[j] < arr[j -1])
                {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
        }
    }
    

    这里面将总结了常用的排序法,并且还有动图表示,很形象

    展开全文
  • 概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因...快速排序:是目前基于比较内部排序中被认为是最好的方法,当待排序关键字是随机分布时,快速排序的平均时间最短; 1....

    概述

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

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

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

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

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

    基本思想:

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

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

    直接插入排序示例:

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

    算法的实现:
    [cpp] view plain copy

    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-路插入排序。

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

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

    基本思想:

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

    操作方法:

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

    希尔排序的示例:

    算法实现:

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

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

    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。希尔排序方法是一个不稳定的排序方法。

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

    基本思想:

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

    简单选择排序的示例:

    操作方法:

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

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

    以此类推…

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

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

    算法实现:
    [cpp] view plain copy

    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]趟循环即可。具体实现如下:
    [cpp] view plain copy

    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;   
      
        }   
    }  
    
    1. 选择排序—堆排序(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

    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 )。

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

    基本思想:

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

    冒泡排序的示例:

    算法的实现:

    [cpp] view plain copy

    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位置即可。

    改进后算法如下:
    [cpp] view plain copy

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

    改进后的算法实现为:
    [cpp] view plain copy

    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值,后移一位  
        }   
    }   
    
    1. 交换排序—快速排序(Quick Sort)

    基本思想:

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

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

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

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

    快速排序的示例:

    (a)一趟排序的过程:

    (b)排序的全过程

    算法的实现:

    递归实现:
    [cpp] view plain copy

    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 左右时,改进算法的性能最佳。算法思想如下:
    [cpp] view plain copy

    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);  
      
    }  
    
    1. 归并排序(Merge Sort)

    基本思想:

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

    归并排序示例:

    合并方法:

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

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

    [cpp] view plain copy

    //将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 个元素按关键码有序的表。
    [cpp] view plain copy

    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);  
      
    }  
    

    两路归并的递归算法
    [cpp] view plain copy

    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);  
    }  
    
    1. 桶排序/基数排序(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, i10]的整数,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]和rj都满足下列有序关系:

    其中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

    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、如果是数字时,最好是无符号的,否则将增加相应的映射复杂度,可先将其正负分开排序。

    展开全文
  • 排序(Sorting)是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,...由于待排序的记录数量不同,使得排序过程中涉及的存储器不同,可将排序方法划分为两大类:内部排序和外部排序。

    排序(Sorting)是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。


    文章目录


    由于待排序的记录数量不同,使得排序过程中涉及的存储器不同,可将排序方法划分为两大类:

    • 内部排序,是指待排序列完全存放在内存中所进行的排序过程,适合不太大的元素序列。
    • 外部排序,指的是大文件的排序,即待排序的记录存储在外存储器上,待排序的文件无法一次装入内存,需要在内存和外部存储器之间进行多次数据交换,以达到排序整个文件的目的。

    九大内部排序:直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序以及基数排序。

    算法稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的。

    注:事实上,基数排序不是基于比较的。


    内部排序可分为五大类,插入排序、交换排序、选择排序、归并排序和基数排序。导图关系如下:
    这里写图片描述


    #1.直接插入排序

    **直接插入排序(Straight Insertion Sort)**是一种最简单的排序方法,它的基本操作是将一个记录插入到已排好序的有序表中,从而得到一个新的、记录数增1的有序表。

    这里写图片描述

    void InsertSort(char A[], int n)
    {
    	int i,j;
    
    	for (i = 2; i <= n; i++)
    	{
    		if (A[i] < A[i-1])
    		{
    			A[0] = A[i];     //复制为哨兵,A[0]不存放元素
    			for (j = i-1; A[0] < A[j]; j--)    //从后往前查待插入位置
    			{
    				A[j+1] = A[j];
    			}
    			A[j+1] = A[0];
    		}
    	}
    }
    

    #2.折半插入排序

    在直接插入排序基础上,对前面有序部分采用折半查找,减少了比较元素的次数。但有个要求,必须是顺序存储的线性表

    这里写图片描述

    void InsertSort2(char A[], int n)
    {
    	int i,j,low,high,mid;
    
    	for (i = 2; i <= n; i++)
    	{
    		A[0] = A[i];     
    		low = 1; high = i-1;
    
    		while (low <= high)    //折半查找
    		{
    			mid = (low+high)/2;
    
    			if (A[mid] > A[0])
    				high = mid-1;
    			else
    				low = mid+1;
    		}
    
    		for (j = i-1; j >= high+1; j--)    
    		{
    			A[j+1] = A[j];
    		}
    
    		A[high+1] = A[0];
    	}
    }
    

    #3.希尔排序

    **希尔排序(Shell’s Sort)**又称“缩小增量排序”,它是一种属于插入排序类的方法,但在时间效率上较前述几种算法有较大改进。

    希尔排序的基本思想是:先将待排序表分割成若干个“特殊”子表,分别进行直接插入排序,当整个表中元素已呈现“基本有序”时,再对全体记录进行一次直接插入排序。希尔排序的分析是一个复杂的问题,因为它的时间是所取“增量”序列的函数,这涉及一些数学上尚未解决的难题。

    注意:希尔排序最后一个增量一定等于1。

    这里写图片描述

    void ShellSort(char A[], int n)
    {
    	int i,j,dk;
    
    	for (dk = n/2; dk >= 1; dk /= 2)  //dk是步长
    	{
    		for (i = dk+1; i <= n; ++i)
    		{
    			if (A[i] < A[i-dk])
    			{
    				A[0] = A[i];   //A[0]不使用,充当暂存器
    				for (j = i-dk; j > 0 && A[0] < A[j]; j-=dk)
    				{
    					A[j+dk] = A[j];
    				}
    				A[j+dk] = A[0];
    			}
    		}
    	}
    }
    

    #4.冒泡排序

    冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。

    这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端,故名。

    这里写图片描述

    void BublleSort(char A[], int n)
    {
    	int i,j;
    	bool flag;
    
    	for (i = 0; i < n-1; i++)
    	{
    		flag = false;
    		for (j = n-1; j > i; j--)
    		{
    			if (A[j-1] > A[j])
    			{
    				swap(A[j-1],A[j]);
    				flag = true;
    			}
    		}
    		if (!flag)
    			return;
    	}
    }
    

    #5.快速排序

    **快速排序(Quicksort)**是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1962年提出。

    它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

    这里写图片描述

    //划分——每次划分唯一确定一个元素位置
    int Partition(int A[], int low, int high)
    {
    	int pivot = A[low];  //一般采用严蔚敏教材版本,以第一个位置为基准
    
    	while (low < high)
    	{
    		while (low < high && A[high] >= pivot)
    		{
    			--high;
    		}
    		A[low] = A[high];  //将比基准小的元素移动到左端
    
    		while (low < high && A[low] <= pivot)
    		{
    			++low;
    		}
    		A[high] = A[low];  //将比基准小的元素移动到右端
    	}
    	A[low] = pivot;
    
    	return low;
    }
    
    //快排——平均时间复杂度O(log2n)
    void QuickSort(int A[], int low, int high)
    {
    	int pivotpos;
    
    	if (low < high)
    	{
    		pivotpos = Partition(A,low,high);
    		//依次对划分后的子表递归排序
    		QuickSort(A,low,pivotpos-1);
    		QuickSort(A,pivotpos+1,high);
    	}
    }
    

    #6.简单选择排序

    设所排序序列的记录个数为n。i取1,2,…,n-1,从所有n-i+1个记录(Ri,Ri+1,…,Rn)中找出排序码最小的记录,与第i个记录交换。执行n-1趟 后就完成了记录序列的排序。

    这里写图片描述

    void swap(char &a, char &b)
    {
    	char t = a;
    	a = b;
    	b = t;
    }
    
    void SelectSort(char A[], int n)
    {
    	int i,j,min;
    
    	for (i = 0; i < n-1; i++)
    	{
    		min = i;
    		for (j = i+1; j < n; j++)
    		{
    			if (A[j] < A[min])
    				min = j;
    		}
    		if (min != i)
    			swap(A[i],A[min]);
    	}
    }
    

    #7.堆排序

    **堆排序(Heapsort)**是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值,即A[parent[i]] >= A[i]。在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。

    这里写图片描述

    //向下调整堆
    void AdjustDown(char A[], int k, int len)
    {
    	int i;
    	
    	A[0] = A[k];
    	for (i = 2*k; i <= len; i*=2)
    	{
    		if (i < len && A[i] < A[i+1])
    			i++;
    		if (A[0] >= A[i])
    			break;
    		else
    		{
    			A[k] = A[i];
    			k = i;
    		}
    	}
    	A[k] = A[0];
    }
    
    //创建大顶堆
    void BuildMaxHeap(char A[], int len)
    {
    	int i;
    
    	for (i = len/2; i > 0; i--)  //调整堆
    		AdjustDown(A,i,len);
    }
    
    //交换两数
    void swap(char &a, char &b)
    {
    	char t = a;
    	a = b;
    	b = t;
    }
    //char A[] = " abfced";
    //HeapSort(A,strlen(A)-1);
    //堆排序
    void HeapSort(char A[], int len)
    {
    	int i;
    
    	BuildMaxHeap(A,len);  //创建初始堆
    	for (i = len; i > 1; i--)  //把最大值顶到堆顶,再与堆底交换
    	{
    		swap(A[i],A[1]);
    		AdjustDown(A,1,i-1);
    	}
    }
    

    #8.归并排序

    **归并排序(Merge Sort)**是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。

    这里写图片描述

    char A[] = "badcgef";
    char *B = (char*)malloc((strlen(A)+1)*sizeof(char));
    //将A[low...mid]、A[mid+1...high]合并为一个表,合并前A两子表有序
    void Merge(char A[], int low, int mid, int high)
    {
    	int i,j,k;
    
    	for (k = low; k <= high; k++) //将A全部复制到B中
    		B[k] = A[k];
    	for (i = low, j = mid+1, k = i; i <= mid && j <= high; k++)
    	{
    		if (B[i] <= B[j])
    			A[k] = B[i++];
    		else
    			A[k] = B[j++];
    	}
    	while (i <= mid)   //复制未检测完表
    		A[k++] = B[i++];
    	while (j <= high)
    		A[k++] = B[j++];
    }
    //归并排序
    void MergeSort(char A[], int low, int high)
    {
    	if (low < high)
    	{
    		int mid = (low + high)/2;
    		MergeSort(A,low,mid);
    		MergeSort(A,mid+1,high);
    		Merge(A,low,mid,high);
    	}
    }
    

    #9.基数排序

    **基数排序(Radix Sort)**它不是基于比较进行排序的,而是采用多关键字排序思想,借助“分配”“收集”两种操作对单逻辑关键字进行排序。基数排序又分为最高位优先(MSD)排序和最低位优先(LSD)排序。

    这里写图片描述


    #附1:各种内部排序算法性质

    这里写图片描述


    参考文献
    [1] 王道论坛. 数据结构联考复习指导[M]. 北京:电子工业出版社, 2016.
    [2] 严蔚敏, 吴伟民. 数据结构(C语言版)[M]. 北京:清华大学出版社, 2015.

    展开全文
  • 本文提出一种可对任意分布的浮点数进行排序的快速排序方法,它基于浮点数的机编码 具有速度快 实现简单 实用的特点。其时间复杂度为O(n),在对不同分布的随机浮点数进行的排序实验,其速度是快速排序的数倍,同时本...
  • 内部排序指排序记录存放在计算机随机存储器中进行的排序过程,外部排序指,由于待排序的记录数量太大,以致...2、快速排序的基本思想是:从待排记录序列中任取一个记录Ri作为基准(通常取序列中的第一个记录),将所...

        内部排序指排序记录存放在计算机随机存储器中进行的排序过程,外部排序指,由于待排序的记录数量太大,以致排序过程中尚需对外存进行访问的排序过程。

    一、快速排序的基本思想

    1、快速排序(Quick Sorting)又称分区交换排序,是对冒泡排序算法的改进,是一种基于分组进行互换的排序方法。

    2、快速排序的基本思想是:从待排记录序列中任取一个记录Ri作为基准(通常取序列中的第一个记录),将所有记录分成两个序列分组,使排在Ri之前的序列分组的记录关键字都小于等于基准记录的关键字值Ri.key,排在Ri之后的序列分组的记录关键字都大于Ri.key,形成以Ri为分界的两个分组,此时基准记录Ri的位置就是它的最终排序位置。此趟排序称为第一趟快速排序。然后分别对两个序列分组重复上述过程,直到所有记录排在相应的位置上。

    在快速排序中,选取基准常用的方法有:

    (1)选取序列中第一个记录的关键字值作为基准关键字。这种选择方法简单。但是当序列中的记录已基本有序时,这种选择往往使两个序列分组的长度不均匀,不能改进排序的时间性能。

    (2)选取序列中间位置记录的关键字值作为基准关键字。

    (3)比较序列中始端、终端及中间位置上记录的关键字值,并取这三个值中居中的一个作为基准关键字。

    通常取序列中的第一个记录作为关键字。

    3、具体的算法描述如下:

    算法中记录的比较和交换是从待排记录序列的两端向中间进行的。设置两个变量i和j,其初值分别是n个待排序记录中第一个记录的位置号和最后一个记录的位置号。在扫描过程中,变量i,j的值始终表示当前所扫描分组序列的第一个和最后一个记录的位置号。将第一个记录R0作为基准记录放到一个临时变量temp中,将R0的位置空出。每趟快速排序,如下进行:

    (1)从序列最后位置的记录Rj开始依次往前扫描,若存在temp≤Rj.key ,则令j前移一个位置,即j= j-1,如此直到temp>Rj.key或i=j为止。若i<j,则将记录Rj放入Ri 空出的位置(由变量i指示的位置)。此时Rj位置空出(由变量j指示的位置)。

    (2)从序列最前位置的记录Ri开始依次往后扫描,若存在temp≥R[i].key,则令i后移一个位置,即i= i+1,如此比较直到temp<Ri.key或i=j为止。若i<j,则将记录Ri放入Rj 空出的位置(由变量j指示的位置)。此时Ri位置空出(用变量i指示的位置)。使j=j-1,继续进行步骤(1)的操作,即再从变量j所指示的当前位置依次向前比较交换。

    在一趟快速排序中,整个过程交替地从后往前扫描关键字值小的记录和从前往后扫描关键字值大的记录并放置到对应端空出的位置中,又空出新的位置。当从两个方向的扫描重合时,即i=j,就找到了基准记录的存放位置。

    按照快速排序的基本思想,在一趟快速排序之后,需要重复(1),(2),直到找到所有记录的相应位置。显然,快速排序是一个递归的过程。

    如下图中所示,a图为一次快速排序过程,b图为排序全过程。

    二、快速排序的C语言描述

    三、快速排序的C语言实现

    #include"stdio.h"

    #include"stdlib.h"

    #defineOK 1

    #defineMAXSIZE 20

    typedefint KeyType;

    typedefint Status;

    typedefstruct

    {

    KeyTypekey;

    //InfoTypeotherinfo;

    }RedType;

     

    typedefstruct

    {

    RedTyper[MAXSIZE+1];

    intlength;

    }Sqlist;

     

    StatusPartition(Sqlist &L,int low,int high)

    {

    //按从小到大的顺序排列

    L.r[0]=L.r[low];

    int pivotkey;

    pivotkey=L.r[low].key;

    while(low<high)

           {

           while(low<high&&L.r[high].key>=pivotkey)--high;

           L.r[low]=L.r[high];

           while(low<high&&L.r[low].key<=pivotkey)++low;

           L.r[high]=L.r[low];

        }//while

        L.r[low]=L.r[0];

           return low;

    }//Partition

     

    void QSort(Sqlist&L,int low,int high)

    {

    //对顺序表中的子序列L.r[low..high]作快速排序

           if(low<high)

           {

           int pivotloc;

           pivotloc=Partition(L,low,high);

           QSort(L,low,pivotloc-1);

           QSort(L,pivotloc+1,high);

           }//if

    }//QSort

     

    voidQuickSort(Sqlist &L)

    {

    QSort(L,1,L.length);

    }

     

    voidInputL(Sqlist &L)

    {

    printf("inputthe length:\n");

    scanf("%d",&L.length);

    printf("inputthe data needed to sort:\n");

    for(inti=1;i<=L.length;i++)

           scanf("%d",&L.r[i].key);

    }//InputL

     

    intmain()

    {

    SqlistL;

    InputL(L);

    QuickSort(L);

    printf("thedata after sorting is:\n");

    for(inti=1;i<=L.length;i++)

           printf("%d ",L.r[i].key);

    returnOK;

    }

    三、快速排序复杂度分析

    其中,Tpass(n)为对n个记录进行一趟快速排序Partition(L,1,n)所用的时间,从算法

     

                                                                                                                                  上式标为(10-8)

                通常,快速排序被认为是在所有同数量级(O(n*logn))中平均性能最

     只要将该记录和L.r[s]互换即可。采用三者中的中值,可

     此时,可改写如上算法,在一趟排序之后比较分割所得两部分的长度,且先对长度短的子序列中的记录进行快速排序,则栈最大深度为O(log(n))。快速排序算法是不稳定排序,对于有相同关键字的记录,排序后有可能颠倒位置。 

     

    展开全文
  • 快速排序是最流行排序算法,在大多数情况下,快速排序都是最快,执行时间为O(N*logN)级。 快速排序通常比其他算法更快,因为它内部循环在大部分架构上效率很好。快速排序使用分而治之 策略来把一个串行...
  • 稳定的排序方法:如果有两个元素相等,排序前后相对位置不变则是稳定,否则所用的排序方法就是不稳定。 不稳定排序: 选择排序、快速排序、希尔排序、堆排序 (选择排序不稳定:4 (4) 2---- 2 (4) ...
  •  快速排序原理:快速排序是一种速度非常快的排序方法,在待排序列元素任意选取一个元素作为分界点,把所有比这个元素值小数放在左边,把所有比这个元素值大数放在右边。这样一趟排序下来,序列被分为左右两...
  • 另一类是外部排序,指是待排序记录数量很大,以致内容一次不能容纳全部记录,在排序中尚需对外存进行访问排序过程。 内部排序按照排序过程所需工作量来区别话,可分为三类:(1)简单的排序方法,其时间...
  • 快速排序方法中的一次交换可以消除多个逆序。 算法思想:从待排序记录序列中选取一个记录(通常选取第一个记录)为枢轴,其关键字设为k1 然后将其余关键字小于k1的记录移到前面,而将关键字大于k1...
  • 数据结构中的内部排序

    千次阅读 2018-03-11 17:59:58
    概述排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序数据... 快速排序:是目前基于比较内部排序中被认为是最好的方法,当待排序关键字是随机分布时,快速排序的平均时间...
  • 这次我们将会重点关注冒泡排序和快速排序.和上一篇文章一样,这次将对于内部排序这两种思路分别进行介绍,同时也会提出这两种方法之间联系.由简到难,让我们由冒泡排序开始本次探讨吧~~.   ps:忽然发现忘记在...
  • 在Array类,提供内置的排序方法。排序是在软件开发过程,经常遇到问题。通过这些内置方法,可以快速轻便进行排序操作。 Array类提供sort方法对Array实例进行排序。sort方法没有返回值,直接改变Array...
  • 八大排序算法

    万次阅读 多人点赞 2012-07-23 16:45:18
    概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序数据很大,一次不能容纳全部... 快速排序:是目前基于比较内部排序中被认为是最好的方法,当待排序关键字是随机分...
  • 常见内部排序方法的比较以及选择

    千次阅读 2013-04-21 20:38:03
    影响排序效果因素及排序方法的选择 ① 排序记录数目n  若n较小(n直接选择排序或直接插入排序。当记录规模较小时,直接插入排序较好;... 快速排序是目前基于比较内部排序中被认为是最好方法,当待排序
  • 按平均时间将排序分为四类:(1)平方阶(O(n2))排序 一般称为简单排序,例如直接插入、直接选择和冒泡排序; (2)线性对数阶(O(nlgn))排序 如快速、堆和归并排序;...简单排序中直接插入最好,快速排序最快...
  • 基本概念由于待排序记录数量不同,使得排序过程涉及存储器不同,可将排序方法分为两大类:内部排序和外部排序。 内部排序:待排序记录存放在计算机随机存储器进行排序过程。 外部排序:待排序记录数量很...
  • 内部排序算法比较 第一章 问题描述 排序是数据结构重要一个部分也是在...接插入排序冒泡排序简单选择排序快速排序希尔排序堆排序二路归并排序等 以关键码比较次数和移动次数分析其特点并进行比较估算每种算法
  • 对冒泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序这六种常用的内排序方法的掌握,通过对各种排序算法分析,对其关键字比较次数和移动次数进行分析,运用数据结构所学知识将其用程序实现。
  • 按平均时间将排序分为四类: (1)平方阶(O(n2))排序  一般称为简单排序,例如直接插入、直接选择和冒泡排序; ...(2)线性对数阶(O(nlgn))排序 ...简单排序中直接插入最好,快速排序最快,当
  • 由于排序效率在同为O(N*logN)几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用,因此很多软件公司笔试面试,包括像腾讯,微软等知名IT公司都喜欢考这个,还有大大小程序方面...
  • 内排序方法总结

    2012-10-26 10:31:07
    一、按平均时间将排序分为四类 (1)平方阶(O(n2))排序  一般称为简单排序,例如插入、选择和冒泡排序; (2)线性对数阶(O(nlgn))排序  如快速、堆和归并排序;... 简单排序中插入最好,快速排序最快
  • 相同关键字元素前后关系在排序中发生变化,则排序方法是不稳定 反之稳定 无论稳定还是不稳定都能把数据排好序 比较排序和非比较排序 大部分排序都是通过比较来排序 有些不需要 计数排序、基数排序 四类...
  • 快速排序(quick sort)的基本思想:通过一趟排序,将序列中的数据分割为两部分,其中一部分的所有数值都比另一个部分的小;然后按照此种方法,对两部分数据分别进行快速排序,直到参与排序的两部分都有序为止。(有...
  • 这几种排序方法分别为:冒泡排序,选择排序,插入排序,快速排序 1.冒泡排序: 思想:简单说就是想办法把一堆数据最大数不停地往后边排。 代码: &lt;script src="...
  • 内部排序(直接加载到内存进行排序):包括交换式排序(冒泡和快速法)、选择式排序、插入式排序 B.外部排序(因数据量大,需借助外部存储进行排序):包括合并排序、直接合并排序 【冒泡排序:从后向前,依次比较...
  • 哈哈,测试一下不就知道了 先说一下我测试的环境 1,我的测试环境是IE6.0和firefox2.0 2,每种算法有很多种不同的实现方法,下面测试我选择上面网友实现的快速排序算法,只是把内嵌函数搬到了外面 3,算法执行的...
  • 这篇文章是对于 JS 数组排序常见方法的一个总结 : 前置知识 : 排序大分类可以分为两种:内排序和外排序。在排序过程,全部记录存放在内存,则称为内排序,如果排序过程需要使用外存,则称为外排序。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,829
精华内容 731
关键字:

内排序中的快速排序方法