Linux教程網
C++實現的隨機化的快速排序:
- #include <iostream>
- #include <set>
- #include <string>
- void swap(int * a,int * b);
- int partition(int * array_list,int left,int right);
- void Print();
- int random_partition(int * array_list,int left,int right);
- void random_quick_sort(int * array_list,int left,int right);
- const int size = 100;
- //int array_list [] ={2,8,7,1,3,5,6,4};
- int * array_list;
- int main()
- {
- //const int size = 10;
- array_list = new int [sizeof(int)*size];
- srand(0);
- for(int i=0;i<size;i++)
- {/*隨即的填充數組元素*/
- int ran_num=rand()% size;
- array_list[i] = ran_num;
- }
- random_quick_sort(array_list,0,size - 1);
- Print();
- return 0;
- }
-
- void random_quick_sort(int * array_list,int left,int right)
- {
- if(left >= right)
- {
- return ;
- }
- int index = random_partition(array_list,left,right);
- random_quick_sort(array_list,left,index - 1);
- random_quick_sort(array_list,index + 1,right);
- }
- /*隨機化的快速排序對於輸入的元素加入隨機化的成分,使之獲得較好的平均性能*/
- int random_partition(int * array_list,int left,int right)
- {
- srand(left);
- int ran_num=( rand())% right;
- if((ran_num < left ))
- {/*防止出現因為取模後隨機數為0的情況*/
- ran_num = left;
- }
- /*如果,不交換排序區間內的數據,則成為普通的快速排序*/
- swap(&array_list[right],&array_list[ran_num]);
- return partition(array_list,left,right);
- }
- int partition(int * array_list,int left,int right)
- {
- int index = left;
- int pivot = array_list[right];
- for(int i= left ; i< right; i++)
- {
- if(array_list[i] < pivot)
- {
- swap(&array_list[index],&array_list[i]);
- index ++;
- }
- }
- swap(&array_list[right],&array_list[index]);
- //Print();
- return index;
- }
- void swap(int * a,int * b)
- {
- int tmp = *a;
- *a = *b;
- *b = tmp;
- }
- void Print()
- {
- for(int i=0;i< size;i++)
- {
- std::cout<<array_list[i]<<"\t";
- }
- std::cout<<std::endl;
- }
Copyright ©
Linux教程網 All Rights Reserved