快速排序

引言

排序是所有算法里比较基本的算法了，并且非常简单。那么我为什么还要自己再写一遍呢我觉得知识是大家的，只有你掌握了，这个知识才属于你，才能为你所用。所以接下来，我要连续的将所有的算法都做成博文。其目的，一是总结知识，提高自己；二是为大家共享知识，经验。希望大家督促并给予支持。

算法介绍

快速排序是七中排序算法里比较常用的算法.分治法的基本思想是：将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。事实上，快速排序通常明显比其他Ο(n log n) 算法更快。

平均时间复杂度O（n * log n），最坏时间复杂度O（n*n）平均空间复杂度O ( log n )，最坏空间复杂度O( n )如果用于大量数据排序，可能函数栈溢出。

实验数据

单项遍历

双向遍历< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vc3Ryb25nPgo8YnI+CgogICAgICAgICAgICAgICAgICAgIDxpbWcgc3JjPQ=="https://www.cppentry.com/upload_files/article/76/1_ewbxg__.jpg" alt="\">

代码
单向遍历

#include #include #include < windows.h> #include #include using namespace std; // data declare typedef vector IntVector ; size_t const size = 10000 ; // function declare void Initialize( IntVector * &V ); void QuickSort(IntVector * &V,size_t s,size_t e); void Swap(IntVector * &V,size_t i,size_t j); void VectorCout(IntVector * &V); int main() { IntVector * V = new IntVector; DWORD time_s ,time_e; Initialize(V); //VectorCout(V); cout<<"quicksort"< size()); time_e = GetTickCount() ; cout<<"给 "< insert(V->begin(),rand() % 1000 ); } } void QuickSort(IntVector * &V,size_t s,size_t e) { if(V && s < e) { size_t key = s; size_t i, j; for(i = s,j = s + 1; j < e; j++) { if(*(V->begin()+j)<*(V->begin()+key)) { Swap(V,++i,j); } } Swap(V,i,key); QuickSort(V,s,i); QuickSort(V,i+1,e); } } void Swap(IntVector * &V,size_t i,size_t j) { if(i >= 0 && i < V -> size() && j >= 0 && j < V -> size() ) { int d = *(V->begin()+i); *(V->begin()+i) = *(V->begin()+j); *(V->begin()+j) = d; } } void VectorCout(IntVector * &V) { cout<<"data follows"< size(); i++) { cout<<*(V->begin()+i)<<" "; } cout<

双向遍历

#include #include #include #include #include using namespace std; // data declare typedef vector IntVector ; size_t const size = 10000 ; // function declare void Initialize( IntVector * &V ); void QuickSort(IntVector * &V,size_t s,size_t e); void Swap(IntVector * &V,size_t i,size_t j); void SwapInt(size_t &i,size_t &j); void VectorCout(IntVector * &V); int main() { IntVector * V = new IntVector; DWORD time_s ,time_e; Initialize(V); //VectorCout(V); cout<<"quick sort"< size()-1); time_e = GetTickCount() ; cout<<"给 "< insert(V->begin(),rand() % 1000 ); } } // Bi-directed void QuickSort(IntVector * &V,size_t s,size_t e) { if(V && 0 <= s && s < e && e < V->size() ) { size_t key = s; size_t i = e ; while( i != key ) { if( i > key ) { if( *(V -> begin()+i) < *(V -> begin()+key) ) { Swap(V,i,key); SwapInt(i,key); i++; } else i--; } else { if( *(V -> begin()+i) > *(V -> begin()+key) ) { Swap(V,i,key); SwapInt(i,key); i--; } else i++; } } QuickSort(V,s,key-1); QuickSort(V,key+1,e); } } void Swap(IntVector * &V,size_t i,size_t j) { if(i >= 0 && i < V -> size() && j >= 0 && j < V -> size() ) { int d = *(V->begin()+i); *(V->begin()+i) = *(V->begin()+j); *(V->begin()+j) = d; } } void SwapInt(size_t &i,size_t &j) { size_t d = i ; i = j; j = d; } void VectorCout(IntVector * &V) { cout<<"data follows"< size(); i++) { cout<<*(V->begin()+i)<<" "; } cout<

算法之排序-----排序第一篇 快速排序

快速排序

引言

算法介绍

平均时间复杂度O（n * log n），最坏时间复杂度O（n*n）平均空间复杂度O ( log n )， 最坏空间复杂度O( n )如果用于大量数据排序，可能函数栈溢出。

实验数据

代码

算法之排序-----排序第一篇快速排序

平均时间复杂度O（n * log n），最坏时间复杂度O（n*n）平均空间复杂度O ( log n )，最坏空间复杂度O( n )如果用于大量数据排序，可能函数栈溢出。