C语言谁能告诉我 数据结构和算法里 快速排序 是怎么弄的?定义两个指针,和一个关键字 具体怎么弄?
收起
知与谁同
2018-07-22 20:43:08
2886
0
3
条回答
写回答
取消
提交回答
-
快速排序是基于分治思想的排序算法。
一般的快排是把大于第一个数的放到右边,小于第一个数的放到左边,然后再对分成的两部分递归。
很简单的一个算法。
现在这里没有编译器,代码不好敲。如果你理解能力或动手能力比较差非常需要代码的话,就追问吧~~
2019-07-17 22:53:18
-
#include <iostream>
using namespace std;
typedef int T;
void sort(T* a, const int& n){
if(n<=1) return;
int pivot = a[0];
int i=0;
int j=n-1;
while(i<j){
while(i<j && a[j]>=pivot)
j--;
if(i<j)
// a[i++] = a[j];
// swap(a[i++],a[j]);
{ swap(a[i],a[j]);
i++;
}
while(i<j && a[i]<=pivot)
i++;
if(i<j)
// a[j--] = a[i];
// swap(a[j--],a[i]);
{
swap(a[j],a[i]);
j--;
} }
a[i] = pivot;
// sort(a+1,i-1);
// sort(a+i,n-i);
sort(a+1,i);
}
int main()
{
const int N=10240;
int a[N];
for(int i=0; i<N; i++)
a[i]=N-i;
time_t t1=time(NULL);
sort(a,N);
time_t t2=time(NULL);
for(int i=0; i<30; i++)
cout << a[i] << " ";
cout << "t2-t2=" << t2-t1 ;
cout << endl;}
这个就是快速排序吧 找到小的 往前换 ; 找到大的 往后换
2019-07-17 22:53:18
-
int partition(TypeR[], int low, int high){
R[0]=R[low];
pivotkey=R[low].key;
while(low<high){
while(low<high&&R[high].key>=pivotkey)
--high;
R[low]=R[high];
while(low<high&&R[low].key<=pivotkey)
++low;
R[high]=R[low];}
R[low]=R[0];
}
R[low]=R[0];
return low;
}
2019-07-17 22:53:18