二次排序算法
① C++中排序的算法分析(文字分析)
排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大，所以排序算法对算法本身的速度要求很高。
而一般我们所谓的算法的性能主要是指算法的复杂度，一般用O方法来表示。在后面我将给出详细的说明。
对于排序的算法我想先做一点简单的介绍，也是给这篇文章理一个提纲。
我将按照算法的复杂度，从简单到难来分析算法。
第一部分是简单排序算法，后面你将看到他们的共同点是算法复杂度为O(N*N)（因为没有使用word,所以无法打出上标和下标）。
第二部分是高级排序算法，复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种算法因为涉及树与堆的概念，所以这里不于讨论。
第三部分类似动脑筋。这里的两种算法并不是最好的（甚至有最慢的），但是算法本身比较奇特，值得参考（编程的角度）。同时也可以让我们从另外的角度来认识这个问题。
第四部分是我送给大家的一个餐后的甜点——一个基于模板的通用快速排序。由于是模板函数可以对任何数据类型排序（抱歉，里面使用了一些论坛专家的呢称）。
现在，让我们开始吧：
一、简单排序算法
由于程序比较简单，所以没有加什么注释。所有的程序都给出了完整的运行代码，并在我的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)算法，但是通常情况下速度要慢于快速排序（因为要重组堆）。
三、其他排序
1.双向冒泡：
通常的冒泡是单向的，而这里是双向的，也就是说还要进行反向的工作。
代码看起来复杂，仔细理一下就明白了，是一个来回震荡的方式。
写这段代码的作者认为这样可以在冒泡的基础上减少一些交换（我不这么认为，也许我错了）。
反正我认为这是一段有趣的代码，值得一看。
#include <iostream.h>
void Bubble2Sort(int* pData,int Count)
{
int iTemp;
int left = 1;
int right =Count -1;
int t;
do
{
//正向的部分
for(int i=right;i>=left;i--)
{
if(pData[i]<pData[i-1])
{
iTemp = pData[i];
pData[i] = pData[i-1];
pData[i-1] = iTemp;
t = i;
}
}
left = t+1;
//反向的部分
for(i=left;i<right+1;i++)
{
if(pData[i]<pData[i-1])
{
iTemp = pData[i];
pData[i] = pData[i-1];
pData[i-1] = iTemp;
t = i;
}
}
right = t-1;
}while(left<=right);
}
void main()
{
int data[] = {10,9,8,7,6,5,4};
Bubble2Sort(data,7);
for (int i=0;i<7;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
2.SHELL排序
这个排序非常复杂，看了程序就知道了。
首先需要一个递减的步长，这里我们使用的是9、5、3、1（最后的步长必须是1）。
工作原理是首先对相隔9-1个元素的所有内容排序，然后再使用同样的方法对相隔5-1个元素的排序
以次类推。
#include <iostream.h>
void ShellSort(int* pData,int Count)
{
int step[4];
step[0] = 9;
step[1] = 5;
step[2] = 3;
step[3] = 1;
int iTemp;
int k,s,w;
for(int i=0;i<4;i++)
{
k = step[i];
s = -k;
for(int j=k;j<Count;j++)
{
iTemp = pData[j];
w = j-k;//求上step个元素的下标
if(s ==0)
{
s = -k;
s++;
pData[s] = iTemp;
}
while((iTemp<pData[w]) && (w>=0) && (w<=Count))
{
pData[w+k] = pData[w];
w = w-k;
}
pData[w+k] = iTemp;
}
}
}
void main()
{
int data[] = {10,9,8,7,6,5,4,3,2,1,-10,-1};
ShellSort(data,12);
for (int i=0;i<12;i++)
cout<<data[i]<<" ";
cout<<"\n";
}
呵呵，程序看起来有些头疼。不过也不是很难，把s==0的块去掉就轻松多了，这里是避免使用0
步长造成程序异常而写的代码。这个代码我认为很值得一看。
这个算法的得名是因为其发明者的名字D.L.SHELL。依照参考资料上的说法：“由于复杂的数学原因
避免使用2的幂次步长，它能降低算法效率。”另外算法的复杂度为n的1.2次幂。同样因为非常复杂并
“超出本书讨论范围”的原因（我也不知道过程），我们只有结果了。
四、基于模板的通用排序：
这个程序我想就没有分析的必要了，大家看一下就可以了。不明白可以在论坛上问。
MyData.h文件
///////////////////////////////////////////////////////
class CMyData
{
public:
CMyData(int Index,char* strData);
CMyData();
virtual ~CMyData();
int m_iIndex;
int GetDataSize(){ return m_iDataSize; };
const char* GetData(){ return m_strDatamember; };
//这里重载了操作符：
CMyData& operator =(CMyData &SrcData);
bool operator <(CMyData& data );
bool operator >(CMyData& data );
private:
char* m_strDatamember;
int m_iDataSize;
};
////////////////////////////////////////////////////////
MyData.cpp文件
////////////////////////////////////////////////////////
CMyData::CMyData():
m_iIndex(0),
m_iDataSize(0),
m_strDatamember(NULL)
{
}
CMyData::~CMyData()
{
if(m_strDatamember != NULL)
delete[] m_strDatamember;
m_strDatamember = NULL;
}
CMyData::CMyData(int Index,char* strData):
m_iIndex(Index),
m_iDataSize(0),
m_strDatamember(NULL)
{
m_iDataSize = strlen(strData);
m_strDatamember = new char[m_iDataSize+1];
strcpy(m_strDatamember,strData);
}
CMyData& CMyData::operator =(CMyData &SrcData)
{
m_iIndex = SrcData.m_iIndex;
m_iDataSize = SrcData.GetDataSize();
m_strDatamember = new char[m_iDataSize+1];
strcpy(m_strDatamember,SrcData.GetData());
return *this;
}
bool CMyData::operator <(CMyData& data )
{
return m_iIndex<data.m_iIndex;
}
bool CMyData::operator >(CMyData& data )
{
return m_iIndex>data.m_iIndex;
}
///////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////
//主程序部分
#include <iostream.h>
#include "MyData.h"
template <class T>
void run(T* pData,int left,int right)
{
int i,j;
T 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);
}
template <class T>
void QuickSort(T* pData,int Count)
{
run(pData,0,Count-1);
}
void main()
{
CMyData data[] = {
CMyData(8,"xulion"),
CMyData(7,"sanzoo"),
CMyData(6,"wangjun"),
CMyData(5,"VCKBASE"),
CMyData(4,"jacky2000"),
CMyData(3,"cwally"),
CMyData(2,"VCUSER"),
CMyData(1,"isdong")
};
QuickSort(data,8);
for (int i=0;i<8;i++)
cout<<data[i].m_iIndex<<" "<<data[i].GetData()<<"\n";
cout<<"\n";
}
② 排序算法有多少种
排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。
排序就是把集合中的元素按照一定的次序排序在一起。一般来说有升序排列和降序排列2种排序，在算法中有8中基本排序：
(1)冒泡排序；
(2)选择排序；
(3)插入排序；
(4)希尔排序；
(5)归并排序；
(6)快速排序；
(7)基数排序；
(8)堆排序；
(9)计数排序；
(10)桶排序。
插入排序
插入排序算法是基于某序列已经有序排列的情况下，通过一次插入一个元素的方式按照原有排序方式增加元素。这种比较是从该有序序列的最末端开始执行，即要插入序列中的元素最先和有序序列中最大的元素比较，若其大于该最大元素，则可直接插入最大元素的后面即可，否则再向前一位比较查找直至找到应该插入的位置为止。插入排序的基本思想是，每次将1个待排序的记录按其关键字大小插入到前面已经排好序的子序列中，寻找最适当的位置，直至全部记录插入完毕。执行过程中，若遇到和插入元素相等的位置，则将要插人的元素放在该相等元素的后面，因此插入该元素后并未改变原序列的前后顺序。我们认为插入排序也是一种稳定的排序方法。插入排序分直接插入排序、折半插入排序和希尔排序3类。
冒泡排序
冒泡排序算法是把较小的元素往前调或者把较大的元素往后调。这种方法主要是通过对相邻两个元素进行大小的比较，根据比较结果和算法规则对该二元素的位置进行交换，这样逐个依次进行比较和交换，就能达到排序目的。冒泡排序的基本思想是，首先将第1个和第2个记录的关键字比较大小，如果是逆序的，就将这两个记录进行交换，再对第2个和第3个记录的关键字进行比较，依次类推，重复进行上述计算，直至完成第(n一1)个和第n个记录的关键字之间的比较，此后，再按照上述过程进行第2次、第3次排序，直至整个序列有序为止。排序过程中要特别注意的是，当相邻两个元素大小一致时，这一步操作就不需要交换位置，因此也说明冒泡排序是一种严格的稳定排序算法，它不改变序列中相同元素之间的相对位置关系。
选择排序
选择排序算法的基本思路是为每一个位置选择当前最小的元素。选择排序的基本思想是，基于直接选择排序和堆排序这两种基本的简单排序方法。首先从第1个位置开始对全部元素进行选择，选出全部元素中最小的给该位置，再对第2个位置进行选择，在剩余元素中选择最小的给该位置即可；以此类推，重复进行“最小元素”的选择，直至完成第(n-1)个位置的元素选择，则第n个位置就只剩唯一的最大元素，此时不需再进行选择。使用这种排序时，要注意其中一个不同于冒泡法的细节。举例说明：序列58539．我们知道第一遍选择第1个元素“5”会和元素“3”交换，那么原序列中的两个相同元素“5”之间的前后相对顺序就发生了改变。因此，我们说选择排序不是稳定的排序算法，它在计算过程中会破坏稳定性。
快速排序
快速排序的基本思想是:通过一趟排序算法把所需要排序的序列的元素分割成两大块，其中，一部分的元素都要小于或等于另外一部分的序列元素，然后仍根据该种方法对划分后的这两块序列的元素分别再次实行快速排序算法，排序实现的整个过程可以是递归的来进行调用，最终能够实现将所需排序的无序序列元素变为一个有序的序列。
归并排序
归并排序算法就是把序列递归划分成为一个个短序列，以其中只有1个元素的直接序列或者只有2个元素的序列作为短序列的递归出口，再将全部有序的短序列按照一定的规则进行排序为长序列。归并排序融合了分治策略，即将含有n个记录的初始序列中的每个记录均视为长度为1的子序列，再将这n个子序列两两合并得到n/2个长度为2(当凡为奇数时会出现长度为l的情况)的有序子序列；将上述步骤重复操作，直至得到1个长度为n的有序长序列。需要注意的是，在进行元素比较和交换时，若两个元素大小相等则不必刻意交换位置，因此该算法不会破坏序列的稳定性，即归并排序也是稳定的排序算法。
③ VB 关于选择排序算法
'在窗体上增加控件command1,label1，然后复制以下代码
Option Explicit
Dim a(9) As Long
Private Sub Command1_Click()
Dim i As Long, l As Long, n As Long
Dim j As Long, s As String
For i = 0 To 9 '使用选择排序法排序，每次选择最小的数值。
For l = i To 9
If a(i) > a(l) Then
n = a(i)
a(i) = a(l)
a(l) = n
End If
Next l
Print a(i)
s = ""
For j = 0 To 9
s = s & a(j) & vbNewLine
Next
MsgBox s, vbInformation, "阶段排序情况"
Next i
End Sub
Private Sub Form_Load()
a(0) = 564 '给数组a中个数组元素赋值。
a(1) = 78
a(2) = 45
a(3) = 456412
a(4) = 456
a(5) = 1
a(6) = 45 + 79
a(7) = 12
a(8) = 1 * 966
a(9) = 65 / 5
Dim i As Long
For i = 0 To 9
Label1.Caption = Label1.Caption & "第" & CStr(i + 1) & "是：" & CStr(a(i)) & " "
Next i
End Sub
④ 数据结构的排序方法有哪些
冒泡排序，快速排序，堆排序。
⑤ Java 直接插入 排序算法 要怎么应用
直接插入排序流程如下：
1、首先比较数组的前两个数据，并排序；
2、比较第三个元素与前两个排好序的数据，并将第三个元素放入适当的位置；
3、比较第四个元素与前三个排好序的数据，并将第四个元素放入适当的位置；
......
4、直至把最后一个元素放入适当的位置。
举例说明：要排序数组：int[] arr = {7, 2, 6, 5, 9, 4};
第1趟后:[2, 7], 6, 5, 9, 4
第2趟后:[2, 6, 7], 5, 9, 4
第3趟后:[2, 5, 6, 7], 9, 4
第4趟后:[2, 5, 6, 7, 9], 4
第5趟后:[2, 4, 5, 6, 7, 9]
算法分析
空间复杂度O(1)
时间复杂度O(n2)
最差情况：反序，需要移动n*(n-1)/2个元素
最好情况：正序，不需要移动元素
数组在已排序或者是“近似排序”时，插入排序效率的最好情况运行时间为O(n)；
插入排序最坏情况运行时间和平均情况运行时间都为O(n2)。
通常，插入排序呈现出二次排序算法中的最佳性能。
对于具有较少元素（如n<=15）的列表来说，二次算法十分有效。
⑥ 用C++实现二叉排序树的各种算法
#include<stdio.h>
#include<stdlib.h>
#define D 2
#define R 10
#define N 11
typedef int KeyType;
typedef int DataType;
struct Node;
typedef struct Node radixNode;
struct Node
{
KeyType key[D];
/* DataType info; */
radixNode *next;
};
typedef radixNode * radixList;
typedef struct QueueNode
{
radixNode *f;
radixNode *e;
} Queue;
Queue queue[R];
void display(radixNode *plist)
{
int i;
radixNode *p;
p=plist->next;
while(p!=NULL)
{
printf("->");
for(i=0;i<D;i++)
printf("%1d",p->key[i]);
p=p->next;
}
printf("\n");
}
void radixSort(radixNode *plist,int d,int r)
{
int i,j,k;
radixNode *p,*head;
head=plist->next;
for(j=d-1;j>=0;j--)
{
p=head;
for(i=0;i<r;i++)
{
queue[i].f=NULL;
queue[i].e=NULL;
}
while(p!=NULL)
{
k=p->key[j];
if(queue[k].f==NULL)
queue[k].f=p;
else
(queue[k].e)->next=p;
queue[k].e=p;
p=p->next;
}
i=0;
while(queue[i].f==NULL)
i++;
p=queue[i].e; head=queue[i].f;
for(i++;i<r; i++)
if(queue[i].f!=NULL)
{
p->next=queue[i].f;
p=queue[i].e;
}
p->next=NULL;
printf("j=%d",j);
}
plist->next=head;
}
void main()
{
radixNode *p,*q,*head;
int a[]={30,12,20,17,40,60,34,42,29,35,47};
int i;
p=(radixNode *) malloc(sizeof(struct Node));
head=p;
p->next=NULL;
printf("test...\n");
for(i=0;i<11;i++)
{
q=(radixNode *) malloc(sizeof(struct Node));
q->key[0]=a[i]/10;
q->key[1]=a[i]%10;
q->next=NULL;
p->next=q;
p=p->next;
}
printf("before:\n");
display(head);
printf("\n");
radixSort(head,D,R);
printf("after:\n");
display(head);
}
⑦ 用归并排序算法对序列1234567需要几次
排序三次
归并排序的方法就是分组排序
假设序列是5,3,7,2,1,4,6
第一次排序每组为2个元素，即分为4组（7/2取上整等于4），分别为【5,3】、【7,2】、【1,4】、【6】，对每一组进行排序；
第一次排序后序列是3,5,2,7,1,4,6
第二次排序每组为4个元素，即分为2组（7/2/2取上整，实际上是第一次分的4组两两合并，即4/2取上整等于2），分别为【3,5,2,7】、【1,4,6】
第二次排序后序列是2,3,5,7,1,4,6
第三次排序每组为8个元素，即只有1组，排序完后就是1,2,3,4,5,6,7了
归并排序第N次排序每组为2^N个，假设有S个元素，一共需要排序Y次，那么最后一次排序每组就是2^Y个，令2^Y>=S，答案很容易就知道了
⑧ 二叉排序算法的实现
#include<iostream>
#include<deque>
#include<algorithm>
using namespace std;
struct BinaryNode
{
char ch;//数据域
BinaryNode *leftChild;//左子节点
BinaryNode *rightChild;//右子节点
BinaryNode(BinaryNode *left=NULL,BinaryNode *right=NULL)
{
rightChild=right;
leftChild=left;
}
BinaryNode(char chz,BinaryNode *left=NULL,BinaryNode *right=NULL)
{
ch=chz;
leftChild=left;
rightChild=right;
}
};
class BinaryTree
{
private:
BinaryNode *root; //根节点
char ref;
void preOrder(BinaryNode *p); //前序遍历
void levelOrder(BinaryNode *p); //层序遍历
void CreateTree(BinaryNode *&p); //根据前序遍历建立二叉树
void deleteTree(BinaryNode *p); //释放二叉树
BinaryNode* CreateBinary(char *VLR,char *LVR,int preStart,int inStart,int n); //根据二叉树的前序遍历和中序遍历建立二叉树
public:
BinaryTree(){root=NULL;ref='#';} //建立空二叉树
~BinaryTree(); //析构函数
void preOrder(); //前序遍历
void levelOrder(); //层序遍历
void CreateTree(); //根据前序遍历建立二叉树
void CreateBinary(char *VLR,char *LVR,int n); //用二叉树的前序遍历与后序遍历建立二叉树
};
void BinaryTree::deleteTree(BinaryNode *p)
//私有函数,释放二叉树
{
if(p!=NULL)
{
deleteTree(p->leftChild);
deleteTree(p->rightChild);
delete p;
}
}
BinaryTree::~BinaryTree() //析构函数
{
deleteTree(root);
}
void BinaryTree::preOrder(BinaryNode *p) //私有函数，前序遍历
{
if(p!=NULL)
{
cout<<p->ch<<" ";
preOrder(p->leftChild);
preOrder(p->rightChild);
}
}
void BinaryTree::preOrder() //前序遍历
{
preOrder(root);
}
void BinaryTree::levelOrder(BinaryNode *p) //私有函数，层序遍历
{
deque<BinaryNode*> level; //利用队列实现
BinaryNode *q=NULL;
if(p!=NULL)
{
level.push_back(p);
}
while(!level.empty())
{
q=level.front();
cout<<q->ch<<" ";
level.pop_front();
if(q->leftChild!=NULL)
level.push_back(q->leftChild); //左子树入队列
if(q->rightChild!=NULL)
level.push_back(q->rightChild); //右子树入队列
}
}
void BinaryTree::levelOrder() //层序遍历
{
levelOrder(root);
}
void BinaryTree::CreateTree(BinaryNode *&p) //引用型参数的的用法*&p
{
char item;
cout<<"请输入节点值: ";
cin>>item;
if(item!=ref) //结束标记ref
{
p=new BinaryNode(item);
CreateTree(p->leftChild); //递归建立左子树
CreateTree(p->rightChild); //递归建立右子树
}
else
p=NULL;
}
void BinaryTree::CreateTree()
{
CreateTree(root);
}
BinaryNode* BinaryTree::CreateBinary(char* VLR,char* LVR,int preStart,int inStart,int n) //私有函数，利用二叉树的前序遍历与中序遍历建立二叉树
{
BinaryNode *p=NULL;
if(n>0)
{
char elem=VLR[preStart];
p=new BinaryNode(elem);
int i=0;
while(i<n&&elem!=LVR[inStart+i])
i++;
p->leftChild=CreateBinary(VLR,LVR,preStart+1,inStart,i);
p->rightChild=CreateBinary(VLR,LVR,preStart+i+1,inStart+i+1,n-i-1);
}
return p;
}
void BinaryTree::CreateBinary(char *VLR,char *LVR,int n) //利用二叉树的前序遍历与中序遍历建立二叉树
{
root=CreateBinary(VLR,LVR,0,0,n);
}
int main()
{
BinaryTree tree;
tree.CreateTree();
cout<<"该二叉树的前序遍历为: ";
tree.preOrder();
cout<<endl;
cout<<"该二叉树的层遍序历为: ";
tree.levelOrder();
cout<<endl;
return 0;
}
⑨ 为什么我使用直接选择排序算法 会顶替掉原来的值
34,56,98,78,23,11,9,54,22,71
第一次排序： 9,56,98,78,34,23,11,54,22,71
第二次排序： 9,11,98,78,56,34,23,54,22,71
第三次排序： 9,11,22,98,78,56,34,54,23,71
第四次排序： 9,11,22,23,98,78,56,54,34,71
第五次排序： 9,11,22,23,34,98,78,56,54,71
第六次排序： 9,11,22,23,34,54,98,78,56,71
第七次排序： 9,11,22,23,34,54,56,98,78,71
第八次排序： 9,11,22,23,34,54,56,,71,98,78
第九次排序： 9,11,22,23,34,54,56,,71,78,98
从第2个元素开始，依次与第一个元素作比较，如果比第一个元素小，则交换，否则找下一个元素与第一个元素比较；
从第3个元素开始，重复第2步，直到比较完
⑩ 谁能给我几种排序的具体算法（直接插入，折半插入，冒泡，简单选择，快速，堆，归并排序）
直接插入排序
说明：逐个将后一个数加到前面的排好的序中。在直接插入排序过程中，对其中一个记录的插入排序称为一次
排序；直接插入排序是从第二个记录开始进行的，因此，长度为n的记录序列需要进行n-1次排序才能完成整个
序列的排序。时间复杂度为O(n2)。
void InsertSort(elemtype x[],int n)
/*用直接插入法对x[0]-x[n-1]排序*/
{
int i,j;
elemtype s;
for(i=0;i<n-1;i++)
{
s=x[i+1];
j=i;
while(j>-1&&s.key<x[j].key)
{
x[j+1]=x[j];
j--;
}
x[j+1]=s;
}
}
－－－－－－－－－－－－－－－－－－－－－
希尔排序
说明：希尔排序又称缩小增量排序，增量di可以有各种不同的取法，但最后一次排序时的增量必须为1，最简
单可取di+1=di/2（取小）。时间复杂度为O(n(log2n)2)。
void ShellSort(elemtype x[],int n,intd[],int Number)
/*用希尔排序法对记录x[0]-x[n-1]排序，d为增量值数组*/
/*Number为增量值个数，各组内采用直接插入法排序*/
{
int i,j,k,m,Span;
elemtype s;
for(m=0;m<Number;m++)
{
Span=d[m];
for(k=0;k<Span;k++)
{
for(i=k;i<n-1;i+=Span)/*这个for之后的是“组内采用直接插入法排序”*/
{
s=x[i+Span];
j=i;
while(j>-1&&s.key<x[j].key)
{
x[j+Span]=x[j];
j-=Span;
}
x[j+Span]=s;
}
}
}
}
－－－－－－－－－－－－－－－－－－－－－－－－－－－－
直接选择排序
说明：每次将后面的最小的找出来插入前面的已排好的序中。同理，具有n个记录的序列要做n-1次排序。
时间复杂度为O(n2)。
void SelectSort(elemtype x[],int n)
/*用直接选择排序法对x[0]-x[n-1]排序*/
{
int i,j,Small;
elemtype Temp;
for(i=0;i<n-1;i++)
{
Small=i;
for(j=i+1;j<n;j++)
if(x[j].key<x[Small].key)
Small=j;
if(Small!=i)
{
Temp=x[i];
x[i]=x[Small];
x[Small]=Temp;
}
}
}
－－－－－－－－－－－－－－－－－－－－－－－－－－
冒泡排序
说明：两个两个比较，将大的往后移。通过第一次冒泡排序，使得待排序的n个记录中关键字最大的记录排到
了序列的最后一个位置上。然后对序列中前n-1个记录进行第二次冒泡排序。。。对于n个记录的序列，共需进
行n次冒泡排序。时间复杂度为O(n2)。
void BubbleSort(elemtype x[],int n)
/*用冒泡排序法对x[0]-x[n-1]排序*/
{
int i,j,flag=1;
elemtype Temp;
for(i=1;i<n&&flag==1;i++)
{
flag=0;
for(j=0;j<n-i;j++)
{
if(x[j].key>x[j+1].key)
{
flag=1;
Temp=x[j];
x[j]=x[j+1];
x[j+1]=Temp;
}
}
}
}
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
快速排序
说明：又叫分区交换排序，是对冒泡排序方法的一种改进。时间复杂度为O(nlog2n)。
void QuickSort(elemtype x[],int low,int high)
/*用递归方法对记录x[0]-x[n-1]进行快速排序*/
{
int i,j;
elemtype Temp;
i=low;
j=high;
Temp=x[low];
while(i<j)
{
/*在序列的右端扫描*/
while(i<j&&Temp.key<=x[j].key)j--;
if(i<j)
{
x[i]=x[j];
i++;
}
/*在序列的左端扫描*/
while(i<j&&x[i].key<Temp.key)i++;
if(i<j)
{
x[j]=x[i];
j--;
}
}
x[i]=Temp;
/*对子序列进行快速排序*/
if(low<i-1)QuickSort(x,low,i-1);
if(j+1<high)QuickSort(x,j+1,high);
}
－－－－－－－－－－－－－－－－－－－－－－－－－
归并排序
说明：所谓归并排序就是将两个或两个以上的有序数据序列合并成一个有序数据序列的过程。
时间复杂度为O(nlog2n)。
void merge(r,l,m,h,r1,r2)/*r[l,m]及r[m+1,h]分别有序，归并后置于r2中*/
sqlist r,r2;
int l,m,h;
{
int i,j,k;
k=l;/*k是r2的指示器，i、j分别为s1、s2的指示器*/
i=l;
j=m+1;
while(i<=m&&j<=h)
{
if(r[i].key<=r[j].key)
{
r2[k]=r[i];
i++;
}
else
{
r2[k]=r[j];
j++;
}
k++;
}
if(i>m) /*s1结束*/
while(j<=h)
{
r2[k]=r[j];
j++;k++;
}
else
while(i<=m)
{
r2[k]=r[i];
i++;k++;
}
}