数据结构算法设计C++实现

答案：所谓排序，就是要整理文件中的记录，使之按关键字递增(或递减)次序排列起来。其确切定义如下： 
输入：n个记录R1，R2，…，Rn，其相应的关键字分别为K1，K2，…，Kn。 
输出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。 
这里，我们简单介绍几种排序方法，直接插入排序、希儿排序、冒泡排序、快速排序、直接选择排序，文中所提及的代码在IE6下测试通过。 
直接插入排序基本思想 
假设待排序的记录存放在数组R[1..n]中。初始时，R[1]自成1个有序区，无序区为R[2..n]。从i=2起直至i=n为止，依次将R[i]插入当前的有序区R[1..i-1]中，生成含n个记录的有序区。 
算法描述 
function InsertSort(arr) { //插入排序->直接插入法排序 
var st = new Date(); 
var temp, j; 
for(var i=1; i<arr.length; i++) { 
if((arr[i]) < (arr[i-1])) { 
temp = arr[i]; 
j = i-1; 
do { 
arr[j+1] = arr[j]; 
j--; 
} 
while (j>-1 && (temp) < (arr[j])); 
arr[j+1] = temp; 
}//endif 
} 
status = (new Date() - st) + ' ms'; 
return arr; 
} 
希尔排序基本思想 
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。 
该方法实质上是一种分组插入方法。 
算法描述 

function ShellSort(arr) { //插入排序->希儿排序 
var st = new Date(); 
var increment = arr.length; 
do { 
increment = (increment/3|0) + 1; 
arr = ShellPass(arr, increment); 
} 
while (increment > 1) 
status = (new Date() - st) + ' ms'; 
return arr; 
} 
function ShellPass(arr, d) { //希儿排序分段执行函数 
var temp, j; 
for(var i=d; i<arr.length; i++) { 
if((arr[i]) < (arr[i-d])) { 
temp = arr[i]; j = i-d; 
do { 
arr[j+d] = arr[j]; 
j = j-d; 
} 
while (j>-1 && (temp) < (arr[j])); 
arr[j+d] = temp; 
}//endif 
} 
return arr; 
} 
再举个例子:
#include "iostream.h" 
void shellSort(int *arr, int len, int *p, int len1); 
int main() 
{ 
int num[15]={100,12,20,31,1,5,44,66,61,200,30,80,150,4,8}; 
int i; 
cout<<"待排数据d=(5,3,1): "; 
for(i=0;i<15;i++) 
{ 
cout<<num[i]<<" "; 
} 
int s[3]={5,3,1}; 
shellSort(num,15, s,3); 
cout<<"\n"; 
return 0; 
} 
void shellSort(int *arr, int len, int *p, int len1) 
{ 
for (int i = 0; i < len1; i++) 
{ 
int d = p[i]; 
for (int n = 0; n < d; n ++) 
{ 
for (int j = n + d; j < len; j = j + d) 
{ 
if (arr[j] < arr[j - d]) 
{ 
int tmp = arr[j]; 
for (int k = j - d; k >= 0 && arr[k] > tmp; k = k - d) 
{ 
arr[k + d] = arr[k]; 
} 
arr[k + d] = tmp; 
} 
} 
} 
cout<<"第"<<i+1<<"趟排序结果："; 
for(int m=0;m<15;m++) 
cout<<arr[m]<<" "; 
cout<<"\n"; 
} 
}

冒泡排序基本思想 
将被排序的记录数组R[1..n]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上"飘浮"。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。 

算法描述 
function BubbleSort(arr) { //交换排序->冒泡排序 
var st = new Date(); 
var temp; 
var exchange; 
for(var i=0; i<arr.length; i++) { 
exchange = false; 
for(var j=arr.length-2; j>=i; j--) { 
if((arr[j+1]) < (arr[j])) { 
temp = arr[j+1]; 
arr[j+1] = arr[j]; 
arr[j] = temp; 
exchange = true; 
} 
} 
if(!exchange) break; 
} 
status = (new Date() - st) + ' ms'; 
return arr; 
} 
 
快速排序基本思想 
将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。 
在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。 
算法描述 
function QuickSort(arr) { //交换排序->快速排序 
if (arguments.length>1) { 
var low = arguments[1]; 
var high = arguments[2]; 
} else { 
var low = 0; 
var high = arr.length-1; 
} 
if(low < high){ 
// function Partition 
var i = low; 
var j = high; 
var pivot = arr[i]; 
while(i<j) { 
while(i<j && arr[j]>=pivot) 
j--; 
if(i<j) 
arr[i++] = arr[j]; 
while(i<j && arr[i]<=pivot) 
i++; 
if(i<j) 
arr[j--] = arr[i]; 
}//endwhile 
arr[i] = pivot; 
// end function 
var pivotpos = i; //Partition(arr，low，high); 
QuickSort(arr, low, pivotpos-1); 
QuickSort(arr, pivotpos+1, high); 
} else 
return; 
return arr; 
} 
直接选择排序基本思想 
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果： 
①初始状态：无序区为R[1..n]，有序区为空。 
②第1趟排序 
在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 
…… 
③第i趟排序 
第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[i]交换，使R[1..i]和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 
这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。 
算法描述 
function SelectSort(arr) { //选择排序->直接选择排序 
var st = new Date(); 
var temp; 
for(var i=0; i<arr.length; i++) { 
var k = i; 
for(var j=i+1; j<arr.length; j++) { 
if((arr[j]) < (arr[k])) 
k = j; 
} 
if (k != i){ 
temp = arr[i]; 
arr[i] = arr[k]; 
arr[k] = temp; 
} 
} 
status = (new Date() - st) + ' ms'; 
return arr; 
} 

从运行速度上来看，快速排序是最快的。
 
另外把二分查找算法也放这里算了:
template<class Type> 
int BinarySearch(Type a[],const Type& x,int n) 
{ 
int left=0; 
int right=n-1; 
while(left<=right){ 
int middle=(left+right)/2; 
if (x==a[middle]) return middle; 
if (x>a[middle]) left=middle+1; 
else right=middle-1; 
} 
return -1; 
} 
直接插入排序
template<class T,class E>
void DataSortList<T,E>::InsertSort(int left,int right)
{
    //把从第二个开始到最后一个元素
    //插入到前面排好的序列中去
    for(int i=left+1;i<=right;i++)
    {
        //i是要插入的元素,放入temp中
        Element<T,E> temp=Vector[i];
        //待插入序列的最后一个元素
        int j=i-1;
        //寻找插入的位置
        while(temp<Vector[j] && j>=left)
        {
            //后移
            Vector[j+1]=Vector[j];
            j--;
        };
        //插入的过程
        Vector[j+1]=temp;
    };
};
////////////////////////////////InsertSort()函数结束 
--------------------------------------------------------------------------------------------------
上一个：想找一些C++编程例题
下一个：C++的链表是什么
更多图片编程知识: