Question

使用函数模板编写快速排序算法

Answer 1

//快速排序法
template<typename T>
void Quick_sort(T *data_ptr, int left, int right)
{
int low(left), high(right);
T middle, temp;

middle = data_ptr[(rand()%(right - left + 1)) + left]; //随机产生一个大于等于left且小于等于right的数

do{
while ((data_ptr[low] < middle) && (low < right)) //左扫面找出大于middle的数
low++;

while ((data_ptr[high]) > middle && (high > left)) //右扫面找出小于middle的数
high--;

//数据交换
if (low <= high)
{
temp = data_ptr[low];
data_ptr[low] = data_ptr[high];
data_ptr[high] = temp;
low++;
high--;
}

}while(low <= high); //当下标交错时停止,结束一次排序

//当左边有部分值的时候（left<high），递归左边
if (left < high)
Quick_sort(data_ptr, left, high);

//当右边有部分值的时候（right > low），递归右边
if (right > low)
Quick_sort(data_ptr, low, right);
}

Answer 2

从你的屏幕输出可以看出来。最后一次操作选择了1.就是调用insert
是在insert的函数里出错的。
你从屏幕输入1 2
告诉函数要在第一个元素之前插入2这个值。
看这里：
q=&(L.elem[i-1]); //q指向要插入的位置
for(p=&(L.elem[L.length-1]);p>=q;--p) //p指向最末一个元素,结束条件是 p>=q
*(p+1)=*p; // 从最后一个元素开始依次后移，
*q=e;
++L.length;
这些代码本身是没问题的。

Answer 3

我没用编译器运行了，直接在这里写下吧。如果有错误自己改下吧，我只提供思路。
#include<iostream>
#include<algorithm>
using namespace std;
int a[100];
int main(){
for(int i=0;i<99;i++)
cin>>a[i];
sort(a,a+100); //这个就是快速排序，调用这个函数就可以了，如果用模板，那就另外写一个相应bool 函数，自己去百度找啦
for(int i=0;i<99;i++)
cout<<a[i]; //排序后输出
return 0;
}

Answer 4

qsort(a+1,n,sizeof(a[0]),Comp);
int Comp(const void *p1,const void *p2)
{
return *(int *)p1 - *(int *)p2;
}