注：本篇写一些常见的复杂排序的实现，比如：快速排序，堆排序，归并排序
1，快速排序：
#include<iostream> #include<ctime> #include<cstdlib> using namespace std; void printIn(int* a,int length){ for(int i=0;i<length;i++) cout<<a[i]<<' '; } void swap(int& a,int& b){ //行参为引用，可直接修改实参的值 int temp; temp = a; a = b; b = temp; } int InRandomRange(int a,int b){ // 形参不是引用，不修改实参的值 int randomNumber = rand()%(b-a+1) + a; //生成[a,b]中的随机数 return randomNumber; } // 教材思想 int Partition1(int* arr,int left,int right){ int pivot = arr[left]; //选取第一个元素为基准 while(left<right){ while(left < right && arr[right] >= pivot) //找到第一个小于 tmp 的元素 arr[right] right--; if(left<right) arr[left] = arr[right]; while(left < right && arr[left] <= pivot) //找到第一个大于 tmp 的元素 arr[left] left++; if(left<right) arr[right] = arr[left]; } arr[left] = pivot; //此时 left == right return left; //返回枢纽值的下标 } // 剑指 Offer 思想 int Partition2(int* arr,int start,int end){ int index = InRandomRange(start,end); //随机选择枢纽值 int small = start - 1; //small 始终是左边数组的最后一个元素的下标 swap(arr[index],arr[end]); for(index=start;index<end;index++){ if(arr[index]<arr[end]){ //进入这个 if 语句的 index 指向小于枢纽值的元素 ++small; //small 为在等待放小于枢纽值元素的下标位置 if(small != index) swap(arr[small],arr[index]); //将小于枢纽值的元素放在 small 处 }//if } //for ++small; //把枢纽值放到 small 下标的后面，返回 枢纽值下标位置 swap(arr[small],arr[end]); return small; } void quickSort(int*a,int left,int right){ int pivot; if(left<=right){ pivot = Partition2(a,left,right); quickSort(a,left,pivot-1); quickSort(a,pivot+1,right); } } int main(){ int a[5] = {1,3,2,6,5}; quickSort(a,0,4); printIn(a,5); return 0; }
快排在库函数中的实现（c/c++）：
#include<iostream> #include<algorithm>
#include<queue>
#include<set> using namespace std; int compare(const void* a,const void* b){ // c 中 qsort 有函数指针参数要传递 return (*(int*) a - *(int*) b); } int arr[10] = {12,45,234,64,12,35,63,23,12,55}; //测试数组 int main(){ sort(arr,arr+10); //c++ STL 中的sort :实质是快排实现的 qsort(arr,10,sizeof(int),compare); // c 库函数中的排序，实质是快排，但是速度比 C++ 慢，使用也不够灵活 for(int i=0;i<(sizeof(arr)/sizeof(arr[0]));i++) cout<<arr[i]<<' ';
//优先队列实现排序
priority_queue<int> pq1; // 定义优先队列，先插入，排序好再输出
for(int i=0;i<(sizeof(arr)/sizeof(arr[0]));i++)
pq1.push(arr[i]);
for(int i=0;i<(sizeof(arr)/sizeof(arr[0]));i++)
pq1.push(arr[i]);
for(int i=0;!pq1.empty();i++){
cout<<pq1.top()<<' '; //从大到小输出
pq1.pop();
}
cout<<pq1.top()<<' '; //从大到小输出
pq1.pop();
}
// set 实现排序：set 的底层实现是红黑树，即平衡二叉树，所以对其进行中序遍历即可实现排序操作
set<int> set1;
set1.insert(arr,arr+10);
for(set<int>::iterator p=set1.begin();p!=set1.end();++p)
cout<<*p<<' ';
set1.insert(arr,arr+10);
for(set<int>::iterator p=set1.begin();p!=set1.end();++p)
cout<<*p<<' ';
return 0; }
2,堆排序：
/* 堆排序 arr 从下标 1 开始存储 */ #include<iostream> using namespace std; void swap(int& a,int &b){ int tmp; tmp = a; a = b; b = tmp; } //向上调整 void siftup(int*arr,int u){ int i,p; i = u; for(;;){ if(i==1) break; p = i/2; if(arr[p]>=arr[i]) break; swap(arr[p],arr[i]); i = p; } } //向下调整 void siftdown(int*arr,int l,int u){ int i,c; i=1; for(;;){ c=2*i; if(c>u) break; if(c+1<=u && arr[c+1]>arr[c]) c++; //找出左右孩子中的最大的那个进行交换 if(arr[i]>arr[c]) break; swap(arr[i],arr[c]); i=c; } } // 向上调整建立大根堆 void buildUpBigHeap(int* arr,int n){ for(int i=2;i<=n;i++) siftup(arr,i); } // 向下调整建立大根堆 void buildDownBigHeap(int* arr,int n){ for(int i=n/2;i>=1;i--) siftdown(arr,i,n); } void heapSort(int* arr,int n){ int i; // arr--; //注释两行 arr-- arr++ 的作用是：输入的数组下标从 0 开始，排序完成的数组也是从下标 0 处开始存放 buildUpBigHeap(arr,n); // 也可以选择向下调整建立大根堆，此次选择向上调整建立大根堆 for(i=n;i>=2;i--){ swap(arr[i],arr[1]); //最大值交换到最后 siftdown(arr,1,i-1); } // arr++; } int main(){ int a[6] = {-1,1,3,2,6,5}; //下标从 1 开始，开始时的 -1 作为开始 a[0] 处 heapSort(a,5); for(int i=1;i<=5;i++) cout<<a[i]<<' '; return 0; }
后面的几种排序有空再更新了。。