1.快速排序是最最基本的排序算法之一,时间复杂度是O(nlog2(n))
基本思想:分治法+递归
假设key为该序列的第一个元素,从后往前遍历,找到第一个小于key值的元素,将该元素赋值给左边的起始值,再从前往后遍历,找到第一个大于key值的元素,将其赋值给刚才右边第一个小于key值的值,当low<high,则不断递归,知道有序为止.
在用数组int num[]和C++的vector传递地址时,vector需要传引用,否则,没法得到正确地址,因为vector本质上是一个类对象,因此传值会得不到正确结果,而数组会退化为指针,因此可以直接传值.
template<typename datatype>
void myquicksort(vector<datatype> &vec, int low, int high)//必须传引用,否则出错,因为vector是一个类对象
{
if (low < high)
{
int l = low;
int r = high;
datatype key = vec[l];//记录key值 while (l < r)
{
while (l < r&&key <= vec[r])//从右往左遍历,找到第一个小于key的元素
--r;
vec[l] = vec[r];
while (l < r&&key >= vec[l])//从左往右遍历,找到第一个大于key值的元素
++l;
vec[r] = vec[l];
}
vec[l] = key;//其实此时l=r myquicksort(vec, low, l-);
myquicksort(vec, r + , high);
}
}
int main2()
{
const int len = ;//定义一个常量
vector<int>data;//创建一个vector,存储int类型的元素
for (int i = ; i < len; i++)
{
data.push_back(rand() % );
cout << (data.at(i)) << "\t";
if ((i + ) % == )
cout << endl;
} clock_t start = clock();//使用clock函数需要包含头文件#include<ctime>
myquicksort(data, , len - );
clock_t end = clock();
cout << "排序完成,总共用时:" << (end - start)*1.0 / CLOCKS_PER_SEC << endl;//#define CLOCKS_PER_SEC 1000
for (int i = ; i < len; i++)
{
cout << (data.at(i)) << "\t";
if ((i + ) % == )
cout << endl;
} system("pause");
return ;
}
2.使用数组来传值:
void myquicksort2(int a[], int low, int high)//数组作为函数参数,没有副本机制,退化为指针
{
if (low >= high)//递归终止条件
return;
else
{
int l = low, h = high;
int key = a[l];
while (l<h)
{
while (l < h&&a[h] >= key)
--h;
a[l] = a[h];
while (l < h&&a[l] <= key)
++l;
a[h] = a[l];
}
a[l] = key;
myquicksort2(a, low, l - );
myquicksort2(a, l + , high);
}
}
int main()
{
const int len = ;
int num[len];
for (int i = ; i < len; i++)
{
num[i] = rand() % ;
cout << num[i] << "\t";
if ((i + ) % == )
cout << endl;
}
clock_t t1 = clock();
myquicksort2(num, , len - );
clock_t t2 = clock();
cout << "排序完成,总共用时:" << (t2 - t1)*1.0 / CLOCKS_PER_SEC << endl;
for (int i = ; i < len; i++)
{
cout << num[i] << "\t";
if ((i + ) % == )
cout << endl;
}
system("pause");
return ;
}