排序算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了排序算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1573字,纯文字阅读大概需要3分钟。
内容图文
快速排序
快速排序采用的思想是分治思想,基本的步骤是首先找出一个元素作为基准,然后将所有元素进行分区操作,达到基准左边的元素都不大于基准值,基准右边的元素都不小于基准值,这样的操作称为一次快排,然后进行递归操作,将基准左边的元素进行快排,将基准右边的元素进行快排,最后达到所有元素有序。
我觉得在编码的时候最主要的操作就是编写一遍快排,也就是将比基准小的都放在左边,反之放在右边。具体的代码如下:
int quicksort(vector<int> &v, int left, int right){
if(left < right){
int key = v[left];
int low = left;
int high = right;
while(low < high){
while(low < high && v[high] > key){
high--;
}
v[low] = v[high];
while(low < high && v[low] < key){
low++;
}
v[high] = v[low];
}
v[low] = key;
quicksort(v,left,low-1);
quicksort(v,low+1,right);
}
}
归并排序
归并排序采用的思想也是分治的思想,主要就是将元素分成两个部分,左边进行归并排序,右边进行归并排序,然后将左右两部分进行合并的操作。
编码的时候主要的部分还是合并的操作,主要的代码如下所示:
public class Merge {
// 不要在 merge 函数里构造新数组了,因为 merge 函数会被多次调用,影响性能
// 直接一次性构造一个足够大的数组,简洁,高效
private static Comparable[] aux;
public static void sort(Comparable[] a) {
aux = new Comparable[a.length];
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int lo, int hi) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
sort(a, lo, mid);
sort(a, mid + 1, hi);
merge(a, lo, mid, hi);
}
private static void merge(Comparable[] a, int lo, int mid, int hi) {
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++)
aux[k] = a[k];
for (int k = lo; k <= hi; k++) {
if (i > mid) { a[k] = aux[j++]; }
else if (j > hi) { a[k] = aux[i++]; }
else if (less(aux[j], aux[i])) { a[k] = aux[j++]; }
else { a[k] = aux[i++]; }
}
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
}
原文:https://www.cnblogs.com/noob-l/p/13586225.html
内容总结
以上是互联网集市为您收集整理的排序算法全部内容,希望文章能够帮你解决排序算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。