首页 > 代码库 > C++中的快速排序(使用vector和数组的不同)
C++中的快速排序(使用vector和数组的不同)
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-1); myquicksort(vec, r + 1, high); }}int main2(){ const int len = 30;//定义一个常量 vector<int>data;//创建一个vector,存储int类型的元素 for (int i = 0; i < len; i++) { data.push_back(rand() % 100); cout << (data.at(i)) << "\t"; if ((i + 1) % 10 == 0) cout << endl; } clock_t start = clock();//使用clock函数需要包含头文件#include<ctime> myquicksort(data, 0, len - 1); clock_t end = clock(); cout << "排序完成,总共用时:" << (end - start)*1.0 / CLOCKS_PER_SEC << endl;//#define CLOCKS_PER_SEC 1000 for (int i = 0; i < len; i++) { cout << (data.at(i)) << "\t"; if ((i + 1) % 10 == 0) cout << endl; } system("pause"); return 0;}
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 - 1); myquicksort2(a, l + 1, high); }}int main(){ const int len = 30; int num[len]; for (int i = 0; i < len; i++) { num[i] = rand() % 100; cout << num[i] << "\t"; if ((i + 1) % 10 == 0) cout << endl; } clock_t t1 = clock(); myquicksort2(num, 0, len - 1); clock_t t2 = clock(); cout << "排序完成,总共用时:" << (t2 - t1)*1.0 / CLOCKS_PER_SEC << endl; for (int i = 0; i < len; i++) { cout << num[i] << "\t"; if ((i + 1) % 10 == 0) cout << endl; } system("pause"); return 0;}
C++中的快速排序(使用vector和数组的不同)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。