`
liss
  • 浏览: 844169 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

C++常用排序算法

阅读更多

一、简单排序算法
由于程序比较简单,所以没有加什么注释。所有的程序都给出了完整的运行代码,并在我的VC环境
下运行通过。因为没有涉及MFC和WINDOWS的内容,所以在BORLAND C++的平台上应该也不会有什么
问题的。在代码的后面给出了运行过程示意,希望对理解有帮助。

1.冒泡法:
这是最原始,也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡:
#include <iostream.h>

void BubbleSort(int* pData,int Count)
{
int iTemp;
for(int i=1;i<Count;i++)
{
    for(int j=Count-1;j>=i;j--)
    {
      if(pData[j]<pData[j-1])
      {
        iTemp = pData[j-1];
        pData[j-1] = pData[j];
        pData[j] = iTemp;
      }
    }
}
}

void main()
{
int data[] = {10,9,8,7,6,5,4};
BubbleSort(data,7);
for (int i=0;i<7;i++)
    cout<<data[i]<<" ";
cout<<"\n";
}

倒序(最糟情况)
第一轮:10,9,8,7->10,9,7,8->10,7,9,8->7,10,9,8(交换3次)
第二轮:7,10,9,8->7,10,8,9->7,8,10,9(交换2次)
第一轮:7,8,10,9->7,8,9,10(交换1次)
循环次数:6次
交换次数:6次

其他:
第一轮:8,10,7,9->8,10,7,9->8,7,10,9->7,8,10,9(交换2次)
第二轮:7,8,10,9->7,8,10,9->7,8,10,9(交换0次)
第一轮:7,8,10,9->7,8,9,10(交换1次)
循环次数:6次
交换次数:3次

上面我们给出了程序段,现在我们分析它:这里,影响我们算法性能的主要部分是循环和交换,
显然,次数越多,性能就越差。从上面的程序我们可以看出循环的次数是固定的,为1+2+...+n-1。
写成公式就是1/2*(n-1)*n。
现在注意,我们给出O方法的定义:

若存在一常量K和起点n0,使当n>=n0时,有f(n)<=K*g(n),则f(n) = O(g(n))。(呵呵,不要说没
学好数学呀,对于编程数学是非常重要的!!!)

现在我们来看1/2*(n-1)*n,当K=1/2,n0=1,g(n)=n*n时,1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n)
=O(g(n))=O(n*n)。所以我们程序循环的复杂度为O(n*n)。
再看交换。从程序后面所跟的表可以看到,两种情况的循环相同,交换不同。其实交换本身同数据源的
有序程度有极大的关系,当数据处于倒序的情况时,交换次数同循环一样(每次循环判断都会交换),
复杂度为O(n*n)。当数据为正序,将不会有交换。复杂度为O(0)。乱序时处于中间状态。正是由于这样的
原因,我们通常都是通过循环次数来对比算法。


2.交换法:
交换法的程序最清晰简单,每次用当前的元素一一的同其后的元素比较并交换。
#include <iostream.h>
void ExchangeSort(int* pData,int Count)
{
int iTemp;
for(int i=0;i<Count-1;i++)
{
    for(int j=i+1;j<Count;j++)
    {
      if(pData[j]<pData[i])
      {
        iTemp = pData[i];
        pData[i] = pData[j];
        pData[j] = iTemp;
      }
    }
}
}

void main()
{
int data[] = {10,9,8,7,6,5,4};
ExchangeSort(data,7);
for (int i=0;i<7;i++)
    cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮:10,9,8,7->9,10,8,7->8,10,9,7->7,10,9,8(交换3次)
第二轮:7,10,9,8->7,9,10,8->7,8,10,9(交换2次)
第一轮:7,8,10,9->7,8,9,10(交换1次)
循环次数:6次
交换次数:6次

其他:
第一轮:8,10,7,9->8,10,7,9->7,10,8,9->7,10,8,9(交换1次)
第二轮:7,10,8,9->7,8,10,9->7,8,10,9(交换1次)
第一轮:7,8,10,9->7,8,9,10(交换1次)
循环次数:6次
交换次数:3次

从运行的表格来看,交换几乎和冒泡一样糟。事实确实如此。循环次数和冒泡一样
也是1/2*(n-1)*n,所以算法的复杂度仍然是O(n*n)。由于我们无法给出所有的情况,所以
只能直接告诉大家他们在交换上面也是一样的糟糕(在某些情况下稍好,在某些情况下稍差)。

3.选择法:
现在我们终于可以看到一点希望:选择法,这种方法提高了一点性能(某些情况下)
这种方法类似我们人为的排序习惯:从数据中选择最小的同第一个值交换,在从省下的部分中
选择最小的与第二个交换,这样往复下去。
#include <iostream.h>
void SelectSort(int* pData,int Count)
{
int iTemp;   //一个存储值。
int iPos;    //一个存储下标。
for(int i=0;i<Count-1;i++)
{
    iTemp = pData[i];
    iPos = i;
    for(int j=i+1;j<Count;j++)
    {
      if(pData[j]<iTemp)    //选择排序法就是用第一个元素与最小的元素交换。
      {
        iTemp = pData[j];
        iPos = j;              //下标的交换赋值。
      }
    }
    pData[iPos] = pData[i];
    pData[i] = iTemp;
}
}

void main()
{
int data[] = {10,9,8,7,6,5,4};
SelectSort(data,7);
for (int i=0;i<7;i++)
    cout<<data[i]<<" ";
cout<<"\n";
}
倒序(最糟情况)
第一轮:10,9,8,7->(iTemp=9)10,9,8,7->(iTemp=8)10,9,8,7->(iTemp=7)7,9,8,10(交换1次)
第二轮:7,9,8,10->7,9,8,10(iTemp=8)->(iTemp=8)7,8,9,10(交换1次)
第一轮:7,8,9,10->(iTemp=9)7,8,9,10(交换0次)
循环次数:6次
交换次数:2次

其他:
第一轮:8,10,7,9->(iTemp=8)8,10,7,9->(iTemp=7)8,10,7,9->(iTemp=7)7,10,8,9(交换1次)
第二轮:7,10,8,9->(iTemp=8)7,10,8,9->(iTemp=8)7,8,10,9(交换1次)
第一轮:7,8,10,9->(iTemp=9)7,8,9,10(交换1次)
循环次数:6次
交换次数:3次
遗憾的是算法需要的循环次数依然是1/2*(n-1)*n。所以算法复杂度为O(n*n)。
我们来看他的交换。由于每次外层循环只产生一次交换(只有一个最小值)。所以f(n)<=n
所以我们有f(n)=O(n)。所以,在数据较乱的时候,可以减少一定的交换次数。


4.插入法:
插入法较为复杂,它的基本工作原理是抽出牌,在前面的牌中寻找相应的位置插入,然后继续下一张
#include <iostream.h>
void InsertSort(int* pData,int Count)
{
int iTemp;
int iPos;
for(int i=1;i<Count;i++)
{
    iTemp = pData[i];
    iPos = i-1;
    while((iPos>=0) && (iTemp<pData[iPos]))
    {
      pData[iPos+1] = pData[iPos];
      iPos--;
    }
    pData[iPos+1] = iTemp;
}
}

void main()
{
int data[] = {10,9,8,7,6,5,4};
InsertSort(data,7);
for (int i=0;i<7;i++)
    cout<<data[i]<<" ";
cout<<"\n";
}

倒序(最糟情况)
第一轮:10,9,8,7->9,10,8,7(交换1次)(循环1次)
第二轮:9,10,8,7->8,9,10,7(交换1次)(循环2次)
第一轮:8,9,10,7->7,8,9,10(交换1次)(循环3次)
循环次数:6次
交换次数:3次

其他:
第一轮:8,10,7,9->8,10,7,9(交换0次)(循环1次)
第二轮:8,10,7,9->7,8,10,9(交换1次)(循环2次)
第一轮:7,8,10,9->7,8,9,10(交换1次)(循环1次)
循环次数:4次
交换次数:2次

上面结尾的行为分析事实上造成了一种假象,让我们认为这种算法是简单算法中最好的,其实不是,
因为其循环次数虽然并不固定,我们仍可以使用O方法。从上面的结果可以看出,循环的次数f(n)<=
1/2*n*(n-1)<=1/2*n*n。所以其复杂度仍为O(n*n)(这里说明一下,其实如果不是为了展示这些简单
排序的不同,交换次数仍然可以这样推导)。现在看交换,从外观上看,交换次数是O(n)(推导类似
选择法),但我们每次要进行与内层循环相同次数的‘=’操作。正常的一次交换我们需要三次‘=’
而这里显然多了一些,所以我们浪费了时间。

最终,我个人认为,在简单排序算法中,选择法是最好的。


二、高级排序算法:
高级排序算法中我们将只介绍这一种,同时也是目前我所知道(我看过的资料中)的最快的。
它的工作看起来仍然象一个二叉树。首先我们选择一个中间值middle程序中我们使用数组中间值,然后
把比它小的放在左边,大的放在右边(具体的实现是从两边找,找到一对后交换)。然后对两边分别使
用这个过程(最容易的方法——递归)。

1.快速排序:
#include <iostream.h>

void run(int* pData,int left,int right)
{
int i,j;
int middle,iTemp;
i = left;
j = right;
middle = pData[(left+right)/2]; //求中间值
do{
    while((pData[i]<middle) && (i<right))//从左扫描大于中值的数
      i++;     
    while((pData[j]>middle) && (j>left))//从右扫描大于中值的数
      j--;
    if(i<=j)//找到了一对值
    {
      //交换
      iTemp = pData[i];
      pData[i] = pData[j];
      pData[j] = iTemp;
      i++;
      j--;
    }
}while(i<=j);//如果两边扫描的下标交错,就停止(完成一次)

//当左边部分有值(left<j),递归左半边
if(left<j)
    run(pData,left,j);
//当右边部分有值(right>i),递归右半边
if(right>i)
    run(pData,i,right);
}

void QuickSort(int* pData,int Count)
{
run(pData,0,Count-1);
}

void main()
{
int data[] = {10,9,8,7,6,5,4};
QuickSort(data,7);
for (int i=0;i<7;i++)
    cout<<data[i]<<" ";
cout<<"\n";
}

这里我没有给出行为的分析,因为这个很简单,我们直接来分析算法:首先我们考虑最理想的情况
1.数组的大小是2的幂,这样分下去始终可以被2整除。假设为2的k次方,即k=log2(n)。
2.每次我们选择的值刚好是中间值,这样,数组才可以被等分。
第一层递归,循环n次,第二层循环2*(n/2)......
所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n
所以算法复杂度为O(log2(n)*n)
其他的情况只会比这种情况差,最差的情况是每次选择到的middle都是最小值或最大值,那么他将变
成交换法(由于使用了递归,情况更糟),但是糟糕的情况只会持续一个流程,到下一个流程的时候就很可能已经避开了该中间的最大和最小值,因为数组下标变化了,于是中间值不在是那个最大或者最小值。但是你认为这种情况发生的几率有多大??呵呵,你完全不必担心这个问题。实践证明,大多数的情况,快速排序总是最好的。
如果你担心这个问题,你可以使用堆排序,这是一种稳定的O(log2(n)*n)算法,但是通常情况下速度要慢
于快速排序(因为要重组堆)。


本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/Yidon/archive/2007/10/30/1855520.aspx

 

//选择排序法SelectionSort(int arr[],int n)
template <typename T>
void SelectionSort(T arr[],int n)
{
int smallIndex;   //表中最小元素的下标
int pass,j;       //用来扫描子表的下标
T temp;           //用来交换表元素的临时变量

//pass的范围是0~n-2
for (pass=0;pass<n-1;pass++)
{
   //从下标pass开始扫描子表
   smallIndex=pass;
  
   //j遍历整个子表arr[pass+1]到arr[n-1]
   for(j=pass+1;j<n;j++)

    //如果找到更小的元素,则将该位置赋值给smallIndex
    if(arr[j]<arr[smallIndex])
     smallIndex=j;

   //如果smallIndex和pass不在相同的位置
   //则将子表中的最小项与arr[pass]交换
   if(smallIndex!=pass)
   {
    temp=arr[pass];
    arr[pass]=arr[smallIndex];
    arr[smallIndex]=temp;
   }
}
}

/************************************************************************
双端选择排序算法:是上面选择排序算法的变种,可以定位每个子表中最小和最大元素
并把它们分别放在子表的开头和结尾.
************************************************************************/
//双端选择排序算法函数deSelSort()的实现
template <typename T>
void deSelSort(T arr[],int n)
{
int smallIndex,largeIndex; //表中最小及最大元素的下标
int leftPass=0,rightPass=n-1,i,j;     //用来从表左边及右边扫描子表的下标
T temp;                        //用于交换元素的临时变量

while (leftPass<=rightPass)
{
   //从左边及右边开始扫描子表
   smallIndex=leftPass;
   largeIndex=rightPass;
  
   //j和i遍历整个子表arr[LeftPass]~arr[rightPass]
   for (i=leftPass+1;i<rightPass;i++)
    //如果找到更小的元素,则将该位置赋值给smallIndex
    if (arr[i]<arr[smallIndex])
     smallIndex=i;

   //如果smallIndex和leftPass不在相同的位置
   //则将子表中的最小项与arr[pass]交换
   if (smallIndex!=leftPass)
   {
    temp=arr[leftPass];
    arr[leftPass]=arr[smallIndex];
    arr[smallIndex]=temp;
   }


   for (j=rightPass-1;j>leftPass;j--)
    if(arr[j]>arr[largeIndex])
     largeIndex=j;

   if(largeIndex!=rightPass)
   {
    temp=arr[rightPass];
    arr[rightPass]=arr[largeIndex];
    arr[largeIndex]=temp;
   }

   //从两头收缩子表
   leftPass++;
   rightPass--;
}
}

//自编冒泡法排序算法函数bubbleSort()的实现
template <typename T>
int bubbleSort(T arr[],int n)
{
bool exchanged=false; //是否发生交换
int i,j;              //用于遍历子表的下标
T temp;               //用于交换元素的临时变量

//开始遍历过程,以下标j构成子表,共有n-1个子表
for (j=n-1;j>=0;j--) //j从后往前收缩n-1~0,以构成子表0~n-1,0~n-2,0~n-3..0~1
{
   exchanged=false;
   for (i=0;i<j;i++) //遍历子表范围0~j
   {
   
    if (arr[i]>arr[i+1])
    {
     temp=arr[i];
     arr[i]=arr[i+1];
     arr[i+1]=temp;
     exchanged=true;
    }
   }
   if (!exchanged) return n-j-1;//如果在一次遍历中没有发生交换,则表示已经
                               //排序好,中断遍历过程
}
return n-1-j;
}


//冒泡法排序一般算法函数bubbleSortEx()的实现
template <typename T>
int bubbleSortEx(T arr[],int n)
{
int i,pass;              //用于遍历子表的下标
T temp;               //用于交换元素的临时变量

//开始遍历过程,以下标j构成子表,共有n-1个子表
for (pass=0;pass<n;pass++) //pass从后往后扩大0~n-1,以构成子表0~n-1,0~n-2,0~n-3..0~1
{
   for (i=0;i<n-pass;i++) //遍历子表范围0~n-pass
   {   
    if (arr[i]>arr[i+1])
    {
     temp=arr[i];
     arr[i]=arr[i+1];
     arr[i+1]=temp;
    }
   }
}
return pass;
}



本文转自:http://hi.baidu.com/zhaoyh%5Fch2000/blog/item/479fd93790e6afd7a3cc2b8f.html

分享到:
评论

相关推荐

    C++常用排序算法(C++)

    【C++常用排序算法】 在计算机科学中,排序算法是用于对一组数据进行排列的算法。C++作为一种强大的编程语言,提供了多种实现排序的方法。本文将详细介绍C++中常用的几种排序算法及其实现。 1. **冒泡排序** 冒泡...

    C++ 常用排序算法

    以下是对C++中几种常用排序算法的详细说明: 1. **选择排序(Selection Sort)**: 选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始...

    P251~254C++常用排序算法学习笔记.docx

    C++常用排序算法学习笔记 本文档主要介绍了五种常用的排序算法,分别是sort、random_shuffle、merge、reverse四种算法。这些算法在实际开发中非常重要,需要开发者熟练掌握。 5.3.1 sort sort是C++中最常用的排序...

    C++常用排序算法研究

    根据给定文件的信息,本文将深入探讨C++中几种常用的排序算法,并对其性能进行分析。 ### 一、基本概念 在计算机科学中,排序是一种重要的数据处理技术,它能够有效地组织数据并提高数据检索的效率。C++作为一种...

    C/C++常用排序算法思想说明及源码实现

    选择排序,插入排序,快速排序,冒泡排序,堆排序,希尔排序等各排序算法的源码实现/算法思想/及时间复杂度比较

    C++实现常用排序算法

    在编程领域,排序算法是计算机科学中的基础但至关重要的部分,尤其在C++这样的系统级编程语言中。本文将深入探讨C++实现的几种常见排序算法:冒泡排序、选择排序、插入排序、归并排序、快速排序以及堆排序。 1. **...

    常用c++排序算法(包括插入排序、冒泡排序、选择排序、快速排序、归并排序、希尔排序等)

    各种常用c++排序算法,包括插入排序、冒泡排序、选择排序、快速排序、归并排序、希尔排序等

    7种常用排序算法实现(C++)(冒泡排序、选择排序、直接插入排序、希尔排序、堆排序、归并排序以及快速排序)

    这里我们将深入探讨七种常用的排序算法,并通过C++语言实现它们。这七种算法分别是:冒泡排序、选择排序、直接插入排序、希尔排序、堆排序、归并排序和快速排序。 1. **冒泡排序**: 冒泡排序是最基础的排序算法之...

    关于c++冒泡排序算法

    ### 关于C++冒泡排序算法的深度解析 在计算机科学与编程领域,排序算法是基础且关键的一部分,其中冒泡排序(Bubble Sort)作为最简单直观的排序算法之一,常被用作教学示例,尤其适合初学者理解排序算法的基本原理...

    C++ 排序算法大全

    快速排序在平均情况下的时间复杂度为O(n log n),是实际应用中最常用的排序算法之一。 5. 归并排序(Merge Sort) 归并排序也是基于分而治之的思想,将大数组分成两个小数组,分别排序后再合并成一个有序的大数组。...

    常用排序算法源码

    在编程领域,排序算法是计算机科学中的核心概念,它们用于对数据进行有序排列。这里我们主要探讨五种常见的排序算法,这些算法的源码你可以在提供的压缩包文件中找到:MergeSort(归并排序)、RadixSort(基数排序)...

    C++语言的算法实现包括插入排序冒泡排序堆排序快速排序

    快速排序是C++中最常用的排序算法之一,由英国计算机科学家C.A.R. Hoare提出。它使用分治策略,选择一个基准元素,将数组分为两部分,一部分的所有元素都小于基准,另一部分的元素都大于基准,然后递归地对这两部分...

    C C++常用算法手册-带详细目录书签.pdf

    《C C++常用算法手册-带详细目录书签.pdf》是一本专为C++程序员设计的算法学习资源,旨在帮助读者深入理解并掌握常见的编程算法。这本书包含了丰富的算法实例和详细的解析,使得学习过程更为直观易懂。标签“C++”...

    常用排序算法C++面向对象实现.doc

    【排序算法的C++面向对象实现】 在计算机科学中,排序是处理数据的重要步骤,它旨在将一组无序的数据转化为有序的数据序列。根据处理方式,排序可以分为内部排序和外部排序。内部排序是指整个排序过程都在内存中...

    常用排序算法总结

    排序算法总结,包括冒泡、插入、选择、快速四种

    C++实现常用排序算法(快速,归并,选择,谢尔,堆排序)

    在编程领域,排序算法是数据结构与算法学习中的核心部分,尤其在C++这样的强类型语言中,理解和熟练掌握各种排序算法对提升编程能力至关重要。本文将深入探讨五种常用的排序算法:快速排序、归并排序、选择排序、...

    C C++常用算法手册

    《C C++常用算法手册》是一本专注于C和C++编程语言中常见算法的实用指南。结合C++ STL(Standard Template Library,标准模板库)的使用,这本书为开发者提供了丰富的算法实现和应用示例,旨在提升程序员在解决复杂...

Global site tag (gtag.js) - Google Analytics