http://blog.csdn.net/lixiaomin_235/article/details/2767007
最近复习了一下数据结构的课本，看了一下关于排序的算法，并编写了下面的小程序以练习。其中排序的算法主要包括：直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序和堆排序等几个。
1、 直接插入排序（Straight Insertion Sort）
直接插入排序是稳定的排序方法，它的基本操作是将一个记录插入到已排好的有序表中，从而得到一个新的、记录数增1的有序表。通常为了防止越界，常设r[0]为监视哨。
2、 希尔排序（Shell Sort）
希尔排序是一种不稳定的排序方法，它的基本操作是先选取一个增量dlta，然后对以dlta为增量的一组数据进行直接插入排序，然后逐渐减小dlta，直到dlta=1,进行最后一次直接插入排序，即得到新的有序表。
3、 冒泡排序（Bubble Sort）
冒泡排序是一种稳定的排序方法，它的基本操作是通过两个相邻的数的比较，不断的将最大或最小的数移动到一端，并同时减小比较的范围，进而达到排序的目的。
4、 快速排序（Quick Sort）
快速排序是一种不稳定的排序方法，它的基本操作是通过一趟排序将待排的记录分成独立的两部分，其中一部分记录的关键字均比另一部分小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
5、 简单选择排序（Simple Selection Sort）
简单选择排序就是通过从无序序列中选择最大或最小的按次序放在一边，进而达到排序的目的。
6、 堆排序（Heap Sort）
堆排序是一种不稳定的排序方法，它的基本操作是通过构建一个大根堆或小根堆，然后将顶上最大或最小的与最后一个交换，并从新调整，直到把所以的数字都排完。
程序运行图：
格式说明：所输入的数字以A开头，并以A相隔，以B结尾。
主要程序代码：
1、 由于程序中用到了RichEdit控件，需要在InitInstance()中添加
AfxInitRichEdit();
2、 添加设置Ridio Button按钮控件的相关代码：
void CSortDemoDlg::OnBnClickedInsertsort()
{
m_nSort=0;
}
void CSortDemoDlg::OnBnClickedShellsort()
{
m_nSort=1;
}
void CSortDemoDlg::OnBnClickedBubblesort()
{
m_nSort=2;
}
void CSortDemoDlg::OnBnClickedQuicksort()
{
m_nSort=3;
}
void CSortDemoDlg::OnBnClickedSelectsort()
{
m_nSort=4;
}
void CSortDemoDlg::OnBnClickedHeapsort()
{
m_nSort=5;
}
3、关于排序数字的数据结构定义：
typedef struct SortList{
int data[20];
int nlength;
}SList;
4、直接插入排序的程序：
// Insert Sort
void InsertSort(SList* pList)
{
int swap;
for(int i=0;i<pList->nlength-1;i++)
{
if(pList->data[i]>pList->data[i+1])
{
swap=pList->data[i+1];
pList->data[i+1]=pList->data[i];
int j;
for(j=i-1;pList->data[j]>swap&&j>=0;j--)
pList->data[j+1]=pList->data[j];
pList->data[j+1]=swap;
}
}
}
5、希尔排序的程序：
// Shell Sort
void ShellInsert(SList* pList,int dlta)
{
int swap;
for(int i=0;i<pList->nlength,pList->data[i]>0;++i)
{
for(int u=i;u<pList->nlength-dlta;u+=dlta)
{
if(pList->data[u]>pList->data[u+dlta])
{
swap=pList->data[u+dlta];
pList->data[u+dlta]=pList->data[u];
int j;
for(j=u-dlta;pList->data[j]>swap&&j>=0;j-=dlta)
pList->data[j+dlta]=pList->data[j];
pList->data[j+dlta]=swap;
}
}
}
}
void ShellSort(SList* pList)
{
int dlta=pList->nlength/2;
while(dlta>=1)
{
ShellInsert(pList,dlta);
dlta/=2;
}
}
7、 冒泡排序的程序：
// Bubble Sort
void BubbleSort(SList* pList)
{
int swap;
for(int i=0;i<pList->nlength;i++)
for(int j=0;j<pList->nlength - i-1;j++)
if( pList->data[j]>pList->data[j+1])
{
swap=pList->data[j];
pList->data[j]=pList->data[j+1];
pList->data[j+1]=swap;
}
}
8、快速排序
// Quick Sort
int Partition(SList* pList,int low,int high)
{
int swap,pivotkey;
pivotkey=pList->data[low];
while(low<high)
{
while(low<high && pList->data[high]>=pivotkey)
--high;
swap=pList->data[low];
pList->data[low]=pList->data[high];
pList->data[high]=swap;
while(low<high && pList->data[low]<=pivotkey)
++low;
swap=pList->data[low];
pList->data[low]=pList->data[high];
pList->data[high]=swap;
}
return low;
}
void QSort(SList* pList,int low,int high)
{
if(low<high)
{
int pivotloc;
pivotloc=Partition(pList,low,high);
QSort(pList,low,pivotloc-1);
QSort(pList,pivotloc+1,high);
}
}
void QuickSort(SList* pList)
{
QSort(pList,0,pList->nlength-1);
}
9、简单选择排序的程序：
// Select Sort
int SelectMinKey(SList* pList,int i)
{
int n,MinKey=10000;
for(int j=i;j<pList->nlength;j++)
if(MinKey>pList->data[j])
{
MinKey=pList->data[j];
n=j;
}
return n;
}
void SelectSort(SList* pList)
{
for(int i=0;i<pList->nlength;i++)
{
int n,swap;
n=SelectMinKey(pList,i);
if(i!=n)
{
swap=pList->data[i];
pList->data[i]=pList->data[n];
pList->data[n]=swap;
}
}
}
10、堆排序的程序：
// Heap Sort
typedef SList HeapType;
void HeapAdjust(HeapType* Heap,int s,int m)
{
int rc;
rc=Heap->data[s];
for(int j=2*s;j<=m;j*=2)
{
if(j<m && Heap->data[j]<Heap->data[j+1])
j++;
if(rc>=Heap->data[j])
break;
Heap->data[s]=Heap->data[j];
s=j;
}
Heap->data[s]=rc;
}
void HeapSort(SList* pList)
{
HeapType* Heap;
Heap=ListToHeap(pList);
for(int i=Heap->nlength/2;i>0;i--)
HeapAdjust(Heap,i,Heap->nlength);
for(int i=Heap->nlength;i>1;i--)
{
int swap;
swap=Heap->data[1];
Heap->data[1]=Heap->data[i];
Heap->data[i]=swap;
HeapAdjust(Heap,1,i-1);
}
HeapToList(Heap,pList);
}
11、堆排序程序中还涉及到将SListType与HeapType类型相互转换的程序：
HeapType* ListToHeap(SList* pList)
{
HeapType* Heap=(HeapType*)malloc(sizeof(HeapType));
Heap->data[0]=0;
Heap->nlength=pList->nlength;
int i=0;
while(pList->data[i]!=0)
{
Heap->data[i+1]=pList->data[i];
i++;
}
Heap->data[i+1]=0;
return Heap;
}
void HeapToList(HeapType* Heap,SList* pList)
{
int i=1;
while(Heap->data[i]!=0)
{
pList->data[i-1]=Heap->data[i];
i++;
}
pList->data[i-1]=0;
}
12、关于字符串（CString类型）和整型（int类型）的转换：
// Function for string to int
// str的格式为:输入的数字字符串必须是以A开始，数字之间用A隔开，结尾以B结束
// 如：A153A256A179B
SList* StrToInt(CString str)
{
SList* pList=(SList*)malloc(sizeof(SList));
int i=0;
char* p;
pList->nlength=0;
int strLength=sizeof(str);
p=str.GetBuffer(strLength);
str.ReleaseBuffer();
while(*p!='B')
{
if(*p!='A')
{
p++;
continue;
}
pList->data[i]=atoi(++p);
i++;
pList->nlength++;
}
pList->data[i]=0;
return pList;
}
// Function for int to string
CString IntToStr(SList* pList)
{
CString temp,str="";
int i=0;
while(pList->data[i]!=0)
{
temp.Format("%d",pList->data[i]);
str+="A"+temp;
i++;
}
str+="B";
return str;
}
13、输入字符串格式错误检查程序：
// Function for Checking
BOOL NumCheck(CString str)
{
if(str=="")
{
MessageBox(NULL,"输入不能为空！","Error",0);
return FALSE;
}
char* p=str.GetBuffer(sizeof(str));
if(*p!='A')
{
MessageBox(NULL,"输入格式错误！","Error",0);
return FALSE;
}
while(*(p+1)!='/0')
p++;
if(*p!='B')
{
MessageBox(NULL,"输入格式错误！","Error",0);
return FALSE;
}
return TRUE;
}
14、控件的消息处理函数程序：
void CSortDemoDlg::OnBnClickedOk()
{
// TODO: 在此添加控件通知处理程序代码
CString NumForSort,str;
SList* pList;
m_SortBefore.GetWindowText(NumForSort);
BOOL bReturn=NumCheck(NumForSort);
if(FALSE==bReturn)
goto End;
// Turn the string into int list
pList=StrToInt(NumForSort);
switch(m_nSort)
{
case 0:
//InsertSort
InsertSort(pList);
break;
case 1:
//ShellSort
ShellSort(pList);
break;
case 2:
//BubbleSort
BubbleSort(pList);
break;
case 3:
//QuickSort
QuickSort(pList);
break;
case 4:
//SelectSort
SelectSort(pList);
break;
case 5:
//HeapSort
HeapSort(pList);
break;
}
// Turn the int list into string
str=IntToStr(pList);
m_SortAfter.SetWindowTextA(str);
End:
m_SortBefore.SetFocus();
}
15、输入格式提示功能消息处理函数程序：
BOOL flag=FALSE;
void CSortDemoDlg::OnEnSetfocusRichedit21()
{
// TODO: 在此添加控件通知处理程序代码
if(flag==FALSE)
{
flag=TRUE;
int bReturn=MessageBox("要排序的数字序列的格式为：以大写字母A开头，以A为间隔符，并以大写B为结尾符。如：A49A38A65A97A76A13A27A49B","序列格式",0);
}
}