求c++的插入、交换、快速排序法

求C++快速排序、插入排序代码。要超级详细，每步每个函数都要注析~

sort()//快速排序
STL库 algorithm库
快速排序（升序）：
类似二分，找到任意点（一般是序列中点）
然后把小于中点的放到左边，大于的放到右边
之后，在以同样方法排左右区间（递归）
代码：
#include#includeusing namespace std;int a[501];void q_sort(int s,int e){int m=a[(s+e)/2],l=s,r=e;do{while(a[l]m)r--;if(ll)q_sort(l,r);}int main(){int n;cin>>n;for(int i=1;i>a[i];q_sort(1,n);for(int i=1;i<=n;i++)cout<<a[i]<<" ";return 0;}

//***********************直接插入法**********************************/
# include
#define Max 15
main()
{
int a[Max],i,j,t;
int length = Max-1;
printf("请输入待排序的%d个记录：",length);
for(i=0;i<length;i++)
scanf("%d",&a[i]);
for(i=1;i<length;i++) /*外循环控制趟数，n个数从第2个数开始到最后共进行n-1次插入*/
{
t=a[i]; /*将待插入数暂存于变量t中*/
for( j=i-1 ; j>=0 && t>a[j] ; j-- ) /*在有序序列（下标0 ~ i-1）中寻找插入位置*/
a[j+1]=a[j]; /*若未找到插入位置，则当前元素后移一个位置*/
a[j+1]=t; /*找到插入位置，完成插入*/
}
printf("直接插入排序后的序列：");
for(i=0;i<length;i++)
printf("%d ",a[i]);
printf("
");
}
//***********************快速排序**********************************/
# include #define Max 5
int partions(int a[],int low,int high)
{
int prvotkey=a[low];
a[0]=a[low];
while (low<high)
{
while(low=prvotkey)
--high;
a[low]=a[high];
while (low<high&&a[low]<=prvotkey)
++low;
a[high]=a[low];
}
a[low]=a[0];
return low;
}
void qsort(int a[],int low,int high)
{
int prvotloc;
if(low<high)
{
prvotloc=partions(a,low,high); //将第一次排序的结果作为枢轴
qsort(a,low,prvotloc-1); //递归调用排序 由low 到prvotloc-1
qsort(a,prvotloc+1,high); //递归调用排序 由 prvotloc+1到 high
}
}
void quick_sort(int a[],int n)
{
qsort(a,1,n); //第一个作为枢轴 ，从第一个排到第n个
}


main( )
{
int a[Max],i;
int length = Max-1;
printf(" 这是一个快速排序
");
printf("请输入%d个待排序的记录序列:
",length);
for(i=1;i<length;i++)
scanf("%d",&a[i]);
quick_sort(a,length);
printf("快速排序后的序列:");
for(i=0;i<length;i++)
printf(" %d",a[i]);
printf("
");
}

手头上只有这两个暂时，其它的排序算法书上都有，主函数的部分基本都一样的，把函数调用部分改一下都可以啦！

交换法不知道.
插入法有直接插入,二分插入,二路排序.
快排的也知道.
介绍一下直接插入:
我都用自然话说了也算是算法的一种表示吧.
比如有十个数,首先,你当第一个数是已排好序的.
然后,用第二个数,去往已排好序的序列中去插.
然后再用第三个数去往此序列里插...直到都插入完,此序列为有序的.
如:1,3,5,2,4
1
1,3
1,3,5
1,2,3,5
1,2,3,4,5

然后是二分插入排序,和直接插入排序类似,只不过,每次插入的时候,直接插入排序是从头到尾与待插数比较大小,而二分插入法,用的是折半查找的方式来比较待插入数和已存序列比较大小来找到最体的位置.

二路排序,我不太会.

快排:
将第一个数,当成一个中间的参照,放到一个临时变量里,临时指针指向此参照位置,设置首指针(第二个数开始),尾指针
然后尾指针往前走,找到第一个比参照小的数将此数放到临时指针的位置,然后临时指针指向此数的位置,然后头指针往后走,找到第一个大于等于参照的,然后放到临时指针的位置,然后临时指针指向当前的位置.如此循环,直接头指针大于尾指针.将第一个数(参照数)放入临时指针中,结束第一次排序.然后,将整个序列分成三个序列,一个是参数数前面的序列,参照数自身就是一个序列,且已排好序,参照数后是另一个序列,如果另二个序列里的数的个数不为1,重新按照上面的说明进行排序.这样,直到所有的序列都有一个数的时候,排序结束!快排属于不稳定排序!

//我写的可能有点乱.希望能帮到你!
如果有需要可以M我,我可以提供快排和插入的代码.
交换法和二路排序,不太会!

快速排序
#include <iostream>
using namespace std;
const int N=10;

class Sort
{
public:
void setnumber();
void putnumber();
void quicksort(int p,int r);

private:
int num[N];
int partition(int p,int r);
};

int main()
{
char ch;
Sort test;
do
{
cout<<"QUICK SORT\n====================\n";
test.setnumber();
cout<<"QUICK SORT\n====================\n";
cout<<"Before sort:\n";
test.putnumber();
cout<<"begin sort:\n";
test.quicksort(0,N-1);
test.putnumber();
cout<<"SUCCESS!\n";
cout<<"====================\nPress Y to continue and N to quit:\n";
cin>>ch;
}while(ch=='y'||ch=='Y');
return 0;
}
void Sort::setnumber()
{
int i;
cout<<"Please input "<<N<<" integers:\n";
for(i=0;i<N;i++)
{
cin>>num[i];
}
}
void Sort::putnumber()
{
int i;
for(i=0;i<N;i++)
{
cout<<num[i]<<" ";
}
cout<<endl;
}
void Sort::quicksort(int p,int r)
{ int q;
if(p<r)
{
q=partition(p,r);
//q=partition_descending(p,r);
quicksort(p,q);
quicksort(q+1,r);
}

}
int Sort::partition(int p,int r)
{
int temp,i,j,x;
while(1)
{
j=r;
i=p;
x=num[p];
while(num[j]>x)j--;
while(num[i]<x)i++;
if(i<j)
{
temp=num[j];
num[j]=num[i];
num[i]=temp;
}
else
{
return j;
}
}
}
插入排序
#include <iostream>
using namespace std;

// direct insert sort
template<typename Type>
void inssort(Type *array, int low, int high)
{
int i,j;
Type temp;

for(i=low+1; i<=high; ++i){
temp=array[i];
j=i;
while(j>low && temp<array[j-1] ){
array[j]=array[j-1];
--j;
}
array[j]=temp;
}
}

// binary insert sort
template<typename Type>
void binsort(Type *array, int low, int high)
{
int left,right,mid;
Type temp;
for(int i=low+1;i<=high;i++){
left=low;
right=i-1;
temp=array[i];
while(left<=right){
mid=(left+right)/2;
if(temp<array[mid]){
right=mid-1;
}else{
left=mid+1;
}
}
for(int j=i; j>left; j--)array[j]=array[j-1];
array[left]=temp;
}

}

inline int ceil_half(int const x)
{
int y=x>>1;
return y<<1==x ? y : ++y;
}

//shell sort
template<typename Type>
void shellsort(Type* array, int low, int high)
{
Type temp;
int d=(high-low)/2;
int j;
while(d){
for(int i=low+d; i<=high; i++){
if(array[i]<array[i-d]){
temp=array[i];
for(j=i; j>=low+d; j-=d){
if(temp<array[j-d])array[j]=array[j-d];
else break;
}
array[j]=temp;
}
}
d=d/2;
}
}

int main()
{
int arr[]={23,31,4,9,12,7};
int const n=sizeof(arr)/sizeof(arr[0]);
for(int i=0;i<n;++i) cout<<"arr["<<i<<"]: "<< arr[i]<<endl;
shellsort(arr,0,n);
cout<<"after sort: "<<endl;
for(int i=0;i<n;++i) cout<<"arr["<<i<<"]: "<< arr[i]<<endl;
}

交换排序
#include <iostream>
using namespace std;

template<typename Type>
inline Type Min(Type a, Type b)
{
return a>b ? b : a;
}

template<typename Type>
inline void Swap(Type* array, int x, int y)
{
Type temp;
temp=array[x];
array[x]=array[y];
array[y]=temp;
}

// quick sort
template<typename Type>
void qsort(Type *array, int low, int high)
{
if(low<high){
int lo=low;
int hi=high+1;
Type elem=array[lo];
for(;;){
while(Min(elem, array[++lo])!=elem && lo < high );
while(Min(elem, array[--hi])==elem && low < hi );
if(lo<hi) Swap(array, lo, hi);
else break;
}
Swap(array,low,hi);
qsort(array,low, hi-1);
qsort(array,hi+1, high);
}
}

// another quick sort
template<typename Type>
void qsort2(Type *array, int low, int high)
{
if(low<high){
int lo=low;
int hi=high;
Type elem=array[lo];

while(lo<hi){
while(lo<hi && elem<array[hi] ) hi--;
if(lo<hi){
array[lo]=array[hi];
lo++;
}
while(lo<hi && elem>=array[lo]) lo++;
if(lo<hi){
array[hi]=array[lo];
hi--;
}
}
array[lo]=elem;
qsort2(array,low,lo-1);
qsort2(array,lo+1, high);

}
}

// bubble sort

template<typename Type>
void bubble(Type *array, int low, int high)
{
int done;
for(int i=high; i>=low+1; i--){
done=1;
for(int j=low+1; j<=i; j++){
if(array[j-1]>array[j]){
Swap(array,j-1,j);
done=0;
}
}
if(done==1) break;
}
}

int main()
{
int arr[]={23,31,4,9,12,7};
int n=sizeof(arr)/sizeof(arr[0]);
for(int i=0;i<n;++i) cout<<"arr["<<i<<"]: "<< arr[i]<<endl;
bubble(arr,0,n-1);
cout<<"after sort: "<<endl;
for(int i=0;i<n;++i) cout<<"arr["<<i<<"]: "<< arr[i]<<endl;
}

---

罗定市18876497259： 在C++中数组的排序方法有哪些? - ？
泰倪盐酸： 大体上可以分为四类:插入排序,选择排序和交换排序; 插入排序有:直接插入排序,希尔排序; 选择排序有:直接选择排序,堆排序 交换排序有:冒泡排序,快速排序 如果数组比较大的话也可用归并排序,效率比较高 各种排序方法各有所长,有的效率比较高,有的空间消耗比较小,总的来说,要针对不同的问题选择合适的方法; 另外,我有各种排序的源代码需要的话留下邮箱.是我以前学的时候写的!

罗定市18876497259： C++数组排序有哪几种算法? - ？
泰倪盐酸： 插入排序算法1.从有序数列和无序数列{a2,a3,…,an}开始进行排序;2.处理第i个元素时(i=2,3,…,n) , 数列{a1,a2,…,ai-1}是已有序的,而数列{ai,ai+1,…,an}是无序的.用ai与ai-1,a i-2,…,a1进行比较,找出合适的位置将ai插入;3.重复第二...

罗定市18876497259： 求C++ 快速插入排序法 - ？
泰倪盐酸： #include<vector> using namespace std; typedef vector< int> VECINT; // 根据Vector元素进行排序,算法如下:void InsertSort( VECINT& vecTest, int nSize ) { VECINT::iterator iter; iter = vecTest.begin() + 1; VECINT::iterator iterTemp; VECINT::...

罗定市18876497259： C++中的排序法有哪些??查找法又有哪些?? - ？
泰倪盐酸： 概述 内排序的方法有许多种,按所用策略不同,可归纳为五类:插入排序、选择 排序、交换排序、归并排序和分配排序.其中,插入排序主要包括直接插入排序和希尔排序两种;选择排序主要包括直接选择排序和堆排序;交换排序主要包括...

罗定市18876497259： 插入排序的C++代码 - ？
泰倪盐酸： 【直接插入排序算法】void InsertSort(DataType A[], int n) { //采用直接插入排序的方法对数组A中的n的元素排序 DataType x;//用于交换时的暂存 int i,j,k; for(i=1;i<n;i++) { //找到插入的位置k: k=i; for(j=i-1;j>=0;j--) { if(A[i]>A[j]) { k=j+1; break; } cout<<...

罗定市18876497259： 用C++交换排序 - ？
泰倪盐酸： 所谓交换,就是根据序列中两个记录值的比较结果来对换这两个记录在序列中的位置.交换排序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动.常见的交换排序有冒泡排序(Bubble Sort),鸡尾酒排序(...

罗定市18876497259： C++中的排序方法 - ？
泰倪盐酸： 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法.

罗定市18876497259： 用快速排序法(C++)排序 从小到大排,最好能讲一下原理,谢谢啦 - ？
泰倪盐酸： #include using namespace std;void swap(int& a,int& b) {int c;c=a;a=b;b=c; }void sort(int* a, int n)//快排函数,从小到大 {if(n<=1) return;if(n==2){if(a[1] swap(a[1],a[0]);return;}swap(a[0],a[n/2]);int t = *a;int* L=a+1;//从左向右走,遇到...

罗定市18876497259： 在C++中有哪些排序法? - ？
泰倪盐酸： 本人学习数据结构时看到的不错的总结,共享一下了 文件有一组记录组成,记录有若干数据项组成,唯一标识记录的数据项称关键字; 排序是将文件按关键字的递增(减)顺序排列; 排序文件中有相同的关键字时,若排序后相对次序保持不变...

罗定市18876497259： c++快速排序法 - ？
泰倪盐酸： int qpass(RecordYype r[],int left,int right)/*对记录数组r中的r[left]至r[right]部分进行一趟排序,并得到枢轴的位置,使得排序后的结果满足期之后(前)的记录的关键字均不小于(大于)枢轴记录*/ { x=r[left]; low=left; high=right; while(low<high) { ...