线性表的排序

1. 随机生成元素用rand()函数

2. 选择排序：
void SelectSort(int* pData,int Count)
{
int iTemp;
int iPos;
for(int i=0;i {
iTemp = pData[i];
iPos = i;
for(int j=i+1;j {
if(pData[j] {
iTemp = pData[j];
iPos = j;
}
}
pData[iPos] = pData[i];
pData[i] = iTemp;
}
}

//解释：pData是你获得的线性表；Count是线性表长度，即元素个数

快速排序：
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] 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 if(left run(pData,left,j);
//当右边部分有值(right>i)，递归右半边
if(right>i)
run(pData,i,right);
}

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

3. 重复排序10000次就是调用函数10000次，计算时间可以用clock()函数，例子：
clock_t start,finish;
double totaltime;
start=clock();

…… //把调用排序算法的函数插入到这里

finish=clock();
totaltime=(double)(finish-start)/CLOCKS_PER_SEC

我来解答：答案是D；
快速排序的普遍复杂度是O（nlog2n)那是对散列的数据而言，最差的情况就是n(n-1)/2(在有序情况下）
冒泡很稳定，就是n(n-1)/2
插入排序不稳定，如果是倒序数列恰好每一位都要判断
堆排序
的普遍复杂度跟块排一样，也是很快的
算法
，但是它相对比较稳定，保险就是O(nlog2n)