注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

云水禅心

淡若秋菊何妨瘦, 清到梅花不畏寒.

 
 
 

日志

 
 

C++实现直接插入排序,折半插入排序,希尔排序,冒泡排序,简单选择排序,快速排序,堆排序。  

2012-12-10 14:22:32|  分类: c++ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |


http://blog.csdn.net/yushuai007008/article/details/7163062

[cpp] view plaincopy

    // Sort.cpp : 定义控制台应用程序的入口点。 
    // 
     
    #include "stdafx.h" 
    #include <iostream> 
     
    using namespace std; 
     
    #define MAXSIZE 30//一个用作示例的小顺序表的最大长度 


[cpp] view plaincopy

    /************************************************************************
    方法:直接插入排序
    说明:将数组的第一个元素r[0]当做哨兵单元,不存储有效数字                                                                 
    ************************************************************************/ 
    void InsertSort(int r[],int n) 
    {//作直接插入排序 
        int i,j; 
        for(i=2;i<=n;i++) 
        {  
            r[0]=r[i];      //r[0]用作哨兵单元, 
            j=i-1; 
            while(r[0]<r[j]) //这样j最小值为0 
            {  
                r[j+1]=r[j];    //记录后移 
                j--; 
            }//while 
            r[j+1]=r[0];        //插入到正确位置 
            for(j=1;j<=n;j++)    //输出每趟排序的结果 
            { 
                cout << r[j] << " ";   
            }//for 
            cout << endl; 
        }//for 
    }//InsertSort 


[cpp] view plaincopy

    /************************************************************************
    方法:折半插入排序(Binary Insert Sort)
    说明:将数组的第一个元素r[0]当做哨兵单元,不存储有效数字 ,与直接插入排序相比,
          比较才次数减少,但移动元素的次数并没有减少。
    ************************************************************************/ 
    void BinaryInsertSort(int r[],int n) 
    {//作直接插入排序 
        int i, low, high, mid; 
        for( i = 2; i <= n; i++) 
        {  
            r[0] = r[i];        //r[0]用作哨兵单元, 
            low = 1;  
            high = i-1; 
            while(low <= high)  
            { //寻找插入点,high之后的元素都需要后移 
                mid = (low + high)/2; 
                if (r[mid] > r[0]) 
                { 
                    high = mid - 1; 
                } 
                else 
                { 
                    low = mid + 1; 
                } 
            } 
            for (int j = i - 1; j > high; j--  ) 
            { 
                r[j+1] = r[j];  //记录后移 
            } 
            r[high + 1] = r[0];     //插入到正确位置 
            for(int j = 1; j <= n; j++)  //输出每趟排序的结果 
            { 
                cout << r[j] << " ";   
            } 
            cout << endl; 
        } 
    } 


[cpp] view plaincopy

    /************************************************************************
    方法:希尔(Shell's Sort)排序
    说明:将数组的第一个元素r[0]当做哨兵单元,不存储有效数字 
          先将待排序的记录按一定的增量分成若干组,分别进行直接插入排序,
          增量减小,再进行直接插入排序,循环至增量为1,则待排序序列此时有序
    ************************************************************************/ 
    void ShellSort(int r[],int n) 
    { 
        for (int d = 10; d != 1;) 
        { 
            d = d/2;  //增量序列可以去不同的值,这里取5、2、1(应使增量序列中的值没有除1以外的 
                      //公因子,并且最后一个增量值必须为1。 
            int i,j; 
     
            for(i = 1 + d; i <= n; i++) 
            {  
                r[0] = r[i]; 
                j = i-d; 
                while( r[0] < r[j])  
                {  
                    r[j+d] = r[j];  //记录后移 
                    j -= d; 
                } 
                r[j+d]=r[0];        //插入到正确位置 
            } 
            for(j = 1; j <= n; j++)  //输出每趟排序的结果 
            { 
                cout << r[j] << " ";   
            } 
            cout << endl; 
        } 
    } 


[cpp] view plaincopy

    /************************************************************************
    方法:冒泡排序(交换排序的一种)(Bubble Sort)
    说明:相邻的元素作比较,将较大元素向后移,第一趟将最大元素移至最末尾,
          第二趟将次大元素移至倒数第二位。(注意:此处应用的这个数组下标从1开始计算)
    ************************************************************************/ 
    void BubbleSort(int r[],int n) 
    { 
        for (int i = 1; i < n; i++) 
        { 
            for (int j = 1; j <= n - i; j++) 
            { 
                if (r[j] > r[j + 1]) 
                { 
                    int temp = r[j]; 
                    r[j] = r[j + 1]; 
                    r[j + 1] = temp; 
                } 
            } 
            //输出一趟排序的结果 
            for (int i = 1; i <= n; i++) 
            { 
                cout << r[i] << " "; 
            } 
            cout << endl; 
        } 
    } 


[cpp] view plaincopy

    /************************************************************************
    方法:快速排序(Quick Sort)
    说明:通过一趟排序将待排记录分割成独立的两部分,其中一部分的关键字均比另一部分的关键字
          小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
    ************************************************************************/ 
    void QSort(int r[], int low, int high) 
    { 
        if (low < high) 
        { 
            int i = low, j = high; 
     
            r[0] = r[i];   //用子表的r[0]位置存储枢轴记录 
             
            while (i < j) 
            {//循环结束后,i,j指向同一个位置,这个位置的左面比枢轴元素小 
             //右面比枢轴元素大 
                while (i < j && r[j] >= r[0]) 
                {//从后往前找,找到下一个比枢轴元素小的 
                    j--; 
                } 
                r[i] = r[j];// 将其放到r[i]位置 
     
                while (i < j && r[i] <= r[0]) 
                {//从前往后找,找到下一个比枢轴元素大的 
                    i++; 
                } 
                r[j] = r[i];//将其放到r[j]位置 
            } 
            r[i] = r[0];  //将枢轴元素放到i和j共同指向的那个位置(此时i==j) 
             
            //递归排序枢轴的左右两部分 
            QSort(r, low, i - 1); 
            QSort(r, i + 1, high); 
        } 
    } 
     
    void QuickSort(int r[],int n) 
    { 
        QSort(r, 1, n); 
        //输出排序后的结果 
        for (int i = 1; i <= n; i++) 
        { 
            cout << r[i] << " "; 
        } 
        cout << endl; 
    } 


[cpp] view plaincopy

    /************************************************************************
    方法:简单选择排序(Simple Selection Sort)
    说明:每次排序时,选择最大或者最小项,将其放入适当的位置,反复操作,直到所有数据
          排序完成为止。(注意:此处应用的这个数组下标从1开始计算)
    ************************************************************************/ 
    void SimpleSelectionSort(int r[],int n) 
    { 
        for (int i = 1; i < n; i++)           
        {    
            int min = i; 
     
            for (int j = i + 1; j <= n; j++) 
            { 
                if (r[min] > r[j]) 
                { 
                    min = j;// 寻找当前值最小元素的下标 
                } 
            } 
            int temp = r[i]; 
            r[i] = r[min]; 
            r[min] = temp; 
            //输出一趟排序的结果 
            for (int i = 1; i <= n; i++) 
            { 
                cout << r[i] << " "; 
            } 
            cout << endl; 
        } 
    } 


[cpp] view plaincopy

    /************************************************************************
    方法:堆排序(Heap Sort)(选择排序的一种)
    说明:只需要一个记录大小的辅助空间,每个待排序的记录仅占有一个存储空间。
          用数组根据层次遍历的方式创建一个完全二叉树,设父节点在数组中位置为i,则左子树
          的位置为2i,右子树的位置为2i+1(树从1开始计数)。算法可从第n/2(取下标)开始,
          到第一个元素,若子节点中有比该元素大的元素,则将该子节点(若两个子节点均比父节点大,则去较大的那个)
          与父节点交换。交换后如出现子节点比孙子节点小,则继续上面的交换至叶子节点。
          这样就建立一个最大堆。也可以建立一个最小堆。(注意:此处应用的这个数组下标从1开始计算)
    ************************************************************************/ 
    void HeapAdjust(int r[], int m, int n) 
    { 
        int temp = r[m]; 
        int mm = m; 
        int j(0); 
        for (j = 2*mm; j <= n; j *= 2) 
        { 
            if (j < n && r[j] < r[j + 1]) 
            { 
                j++; 
            } 
            if (r[j] <= temp) 
            { 
                break; 
            } 
            r[mm] = r[j]; 
     
            mm = j; 
        } 
        r[mm] = temp; 
    } 
    ////////////////////////////////////////////////////////////////////////// 
    //对r数组中的前n个数排序(从1开始) 
    void HeapSort(int r[],int n) 
    {   //“筛选”工作可从前n/2的元素开始(n/2取下标) 
        //建立起一个最大堆(最小堆) 
        for (int m = n/2; m > 0; m--) 
        { 
            HeapAdjust(r, m, n); 
        } 
     
        //依次取出最大(小)值,并调整堆仍未最大堆(最小堆) 
        for (int i = n; i > 1; i--) 
        { 
            int temp = r[1]; 
            r[1] = r[i]; 
            r[i] = temp;    //将最后一个元素与第一个元素交换 
            HeapAdjust(r, 1, i - 1); // 调整取出元素之核的堆仍未最大堆(最小堆) 
        } 
     
        //输出排序之后的结果 
        for (int i = 1; i <= n; i++) 
        { 
            cout << r[i] << " "; 
        } 
        cout << endl; 
    } 


[cpp] view plaincopy

    //测试代码 
    int _tmain(int argc, _TCHAR* argv[]) 
    { 
        int n,i;        //待排序的关键字个数 
        int r[MAXSIZE]; 
        cout << "Please input the total count you want to sort: "; 
        cin >> n; 
        cout << "Please input the numbers you want to sort,use space to separate:" << endl; 
        for( i=1 ; i <= n ; i++ )//输入待排序的关键字 
        { 
            cin >> r[i]; 
        } 
        //InsertSort(r,n);  //直接插入排序 
     
        //BinaryInsertSort(r,n);   //折半插入排序 
     
        //ShellSort(r,n);  //希尔排序 
     
        //BubbleSort(r,n);  //冒泡排序 
     
        //SimpleSelectionSort(r,n);  //简单选择排序 
     
        //QuickSort(r, n);  //快速排序 
     
        HeapSort(r, n);   //堆排序 
     
    }
  评论这张
 
阅读(1035)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018