基本排序算法程序实现

简单算法O(n^2)：冒泡法<简单选择排序<直接插入排序（性能比较）

改进算法：希尔排序、堆排序、归并排序、快速排序

数组交换语句swap()

1 void swap(int* sortList,int intA,int intB)
2 {
3     int a=sortList[intA];
4     sortList[intA]=sortList[intB];
5     sortList[intB]=a;
6 }

冒泡法（改进）

void BubbleSort(int* sortList,int len)
{
	bool isOrder=false; //哨兵
	for(int i=0;(i<len-1)&&!isOrder;i++)
	{
		isOrder=true;
		for(int j=len-1;j>=i;j--)
		{
			if(sortList[j]<sortList[j-1])
			{
				swap(sortList,j,j-1);
				isOrder=false;
			}
		}
	}
}

简单选择排序

void SimpleSort(int* sortList, int len)
{
	int minIndex;
	for(int i=0;i<len;i++)
	{
		minIndex=i;
		for(int j=i+1;j<len;j++)
		{
			if(sortList[i]>sortList[j])
				minIndex=j;
		}
		if(minIndex!=i)
			swap(sortList,i,minIndex);
	}
}

直接插入排序

 1 void DirectInsertionSort(int* sortList,int len)
 2 {
 3     int tempInt;
 4     for(int i=1;i<len;i++)
 5     {
 6         if(sortList[i]>sortList[i-1])continue;
 7 
 8         tempInt=sortList[i];
 9         int j;
10         for(j=i-1;sortList[j]>tempInt&&j>=0;j--)
11         {
12             sortList[j+1]=sortList[j];
13         }
14 
15         sortList[j+1]=tempInt;
16     }
17 }

改进算法

希尔排序

 1 void ShellSort(int* sortList,int len)
 2 {
 3     int g=len;
 4     do
 5     {
 6         g=g/3+1;
 7         for(int i=0;i<g;i++)
 8         {
 9             for(int j=i+g;j<len;j+=g)
10             {
11                 if(sortList[j]<sortList[j-g])
12                 {
13                     int temp=sortList[j];
14                     int k=j-g;
15                     while(sortList[k]>temp&&k>=0)
16                     {
17                         sortList[k+g]=sortList[k];
18                         k-=g;                
19                     }
20                     sortList[k+g]=temp;
21                 }
22             }
23         }
24     }while(g>1);
25 }

堆排序（注意数组从1开始）

 1 void HeapSort(int* sortList,int len)
 2 {
 3 
 4     for(int j=len/2;j>0;j--)
 5     {
 6         HeapAdjust(sortList,j,len);
 7     }
 8 
 9     for(int fn=len;fn>1;fn--)
10     {
11         swap(sortList,1,fn);
12         HeapAdjust(sortList,1,fn-1);
13     }
14 }
15 
16 void HeapAdjust(int* sortList,int r,int k)
17 {
18     int temp,j;
19     temp=sortList[r];
20     for(j=2*r;j<=k;j=j*2)
21     {
22         if(j<k&&sortList[j]<sortList[j+1])
23             j++;
24         if(temp>=sortList[j])
25             break;
26         sortList[r]=sortList[j];
27         r=j;
28     }
29     sortList[r]=temp;
30 }

归并排序

递归思想

 1 const int MAXSIZE=10000;
 2 
 3 void MergeSort(int* sortList,int len)
 4 {
 5     MSort(sortList,sortList,0,len-1);
 6 }
 7 
 8 void MSort(int* SR,int* TR,int st,int fn)
 9 {
10     int* TR2=new int[MAXSIZE];
11     int mid;
12     if(st==fn)
13     {
14         TR[st]=SR[st];
15     }
16     else
17     {
18         mid=(st+fn)/2;
19         MSort(SR,TR2,st,mid);
20         MSort(SR,TR2,mid+1,fn);
21         Merge(TR2,TR,st,mid,fn);
22     }
23     delete[] TR2;
24 }
25 
26 void Merge(int* TR2,int* TR,int st,int mid,int fn)
27 {
28   int index,s1,s2;
29   index=st;
30   for(s1=st,s2=mid+1;s1<=mid&&s2<=fn;index++)
31   {
32       if(TR2[s1]<TR2[s2])
33       {
34           TR[index]=TR2[s1++];
35       }
36       else
37       {
38           TR[index]=TR2[s2++];
39       }
40   }
41 
42   if(s1<=mid)
43       for(s1;s1<=mid;s1++)
44           TR[index++]=TR2[s1];
45 
46   if(s2<=fn)
47       for(s2;s2<=fn;s2++)
48           TR[index++]=TR2[s2];
49 }

快速排序

 1 void QuitSort(int* sortList,int len)
 2 {
 3     QSort(sortList,0,len-1);
 4 }
 5 
 6 void QSort(int* sortList,int low,int high)
 7 {
 8     int pivot;
 9     if(low<high)
10     {
11         pivot=Partition(sortList,low,high);
12         QSort(sortList,low,pivot-1);
13         QSort(sortList,pivot+1,high);
14     }
15 }
16 
17 int Partition(int* sortList,int low,int high)
18 {
19     int pivot=sortList[low];
20     while(low<high)
21     {
22         while(high>low&&sortList[high]>=pivot)
23             high--;
24         swap(sortList,low,high);
25         while(high>low&&sortList[low]<=pivot)
26             low++;
27         swap(sortList,low,high);
28     }
29     return low;
30 }