quickSort

xiaoxiao2021-02-28  105

推荐慕课网,刘宇波老师《算法与数据结构》 链接:http://coding.imooc.com/class/71.html quickSort 课堂笔记 /* first */ #include <cstdlib> #include <iostream> #include <ctime> using namespace std; template<typename T> int partition(T arr[],int l,int r) { swap(arr[l],arr[rand()%(r-l+1)+l]); T v = arr[l]; int j = l; for(int i = l+1;i <= r;i++){ if(arr[i] < v){ j++; swap(arr[j],arr[i]); } } swap(arr[l],arr[j]); return j; } template<typename T> void _quickSort(T arr[],int l,int r) { if(l < r){ int p = partition(arr,l,r); _quickSort(arr,l,p-1); _quickSort(arr,p+1,r); } } template<typename T> void quickSort(T arr[],int n) { srand(time(NULL)); _quickSort(arr,0,n-1); } int main(){ int arr[] = {9,8,7,6,5,4,3,2,1}; int n = sizeof(arr)/sizeof(arr[0]); quickSort(arr,n); for(int i = 0;i<n;i++) printf("%d ",arr[i]); printf("\n"); return 0; } /* 初步优化 */ #include<iostream> #include<cstdlib> #include<ctime> using namespace std; template<typename T> int partition2(T arr[],int l,int r) { swap(arr[l],arr[rand()%(r-l+1)+l]); T v = arr[l]; //arr[l+1...i) <= v ,arr[j...r] >= v int i = l+1,j = r; while(true){ while(i <= r && arr[i] < v) i++; while(j >= l+1 && arr[j] > v) j--; if(i > j) break; swap(arr[i],arr[j]); i++,j++; } swap(arr[l],arr[j]); return j; } template<typename T> void _quickSort2(T arr[],int l,int r) { if(l < r){ int p = partition2(arr,l,r); _quickSort2(arr,l,p-1); _quickSort2(arr,p+1,r); } } template<typename T> void quickSort2(T arr[],int n) { srand(time(NULL)); _quickSort2(arr,0,n-1); } int main(){ int arr[] = {9,8,7,6,5,4,3,2,1}; int n = sizeof(arr)/sizeof(arr[0]); quickSort2(arr,n); for(int i = 0;i<n;i++) printf("%d ",arr[i]); printf("\n"); return 0; }
转载请注明原文地址: https://www.6miu.com/read-63135.html

最新回复(0)