快速排序
-
算法:关键就在于 pivot在排序之前就拿出来,空一个位置,然后左右指针交替扫描,遇到不符合情况的就把那个不符合的数字放到空位置,直至左右指针重合,在排序过程中pivot是一直在序列之外的,在一趟排序之后再把pivot放回唯一的空位置就行
-
代码
void fast(vector<int>& arr, int low, int high) { if (low >= high) return; int temp = arr[low]; int i = low; int j = high; while (low < high) { while (arr[high] > temp && low < high) high--; if(low<high) arr[low++] = arr[high]; while (arr[low] < temp && low < high) low++; if(low<high) arr[high--] = arr[low]; } arr[low] = temp; fast(arr, i, low - 1); fast(arr, low + 1, j); }
-
优化
- 选取pivot,应选取较中间的,而不是最大值和最小值
归并排序
-
算法:分治
-
代码:
`#include <iostream> using namespace std; void Merge(int arr[], int low, int mid, int high); void MergeSort(int arr[], int low, int high) { if (low >= high) { return; } // 终止递归的条件,子序列长度为1 int mid = low + (high - low) / 2; // 取得序列中间的元素 MergeSort(arr, low, mid); // 对左半边递归 MergeSort(arr, mid + 1, high); // 对右半边递归 Merge(arr, low, mid, high); // 合并 } void Merge(int arr[], int low, int mid, int high) { //low为第1有序区的第1个元素,i指向第1个元素, mid为第1有序区的最后1个元素 int i = low, j = mid + 1, k = 0; //mid+1为第2有序区第1个元素,j指向第1个元素 int* temp = new int[high - low + 1]; //temp数组暂存合并的有序序列 while (i <= mid && j <= high) { if (arr[i] <= arr[j]) //较小的先存入temp中 temp[k++] = arr[i++]; else temp[k++] = arr[j++]; } while (i <= mid)//若比较完之后,第一个有序区仍有剩余,则直接复制到t数组中 temp[k++] = arr[i++]; while (j <= high)//同上 temp[k++] = arr[j++]; for (i = low, k = 0; i <= high; i++, k++)//将排好序的存回arr中low到high这区间 arr[i] = temp[k]; delete[]temp;//释放内存,由于指向的是数组,必须用delete [] } int main() { int arr[] = { 1,3,5,0,22,33 }; MergeSort(arr, 0, 5); for (int i = 0; i <= 5; i++) { cout << arr[i] << endl; } }`
原文地址:http://www.cnblogs.com/hithin/p/16866187.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性