排序算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了排序算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2389字,纯文字阅读大概需要4分钟。
内容图文
![排序算法](/upload/InfoBanner/zyjiaocheng/1335/ace76e294a3a4cdeb1d64f5d679b2e28.jpg)
选择排序:O(n^2) 不稳定
a={5,2,8,4,9,1}
第一趟i=0:最小1,1和5交换:1, 2,8,4,9,5
第二趟i=1:最小2, 1,2, 8,4,9,5
第三趟i=2:最小4,4和8交换:1,2,4, 8,9,5
第四趟i=3:最小5,5和8交换:1,2,4,5, 9,8
第五趟i=4:最小8,8和9交换:1,2,4,5,8, 9
public static void selectSort(int[] a){ for (int i = 0; i < a.length; i++) { int k=i; for (int j = k; j < a.length; j++) { if(a[k]>a[j]){ k=j; } } if(i!=k){ int temp = a[i]; a[i]=a[k]; a[k]=temp; } } }
堆排序:o(nlogn) 不稳定
冒泡排序:O(n)~O(n^2) 稳定
public static void bubbleSort(int[] a){ for (int i = 0; i < a.length; i++) { for (int j = 0; j < a.length-i-1; j++) { if(a[j]>a[j+1]){ int temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; } } } }
快速排序:O(nlogn) 不稳定
比如:对R={37, 40, 38, 42, 461, 5, 7, 9, 12}进行一趟快速排序的过程如下(注:下面描述的内容中元素下表从 0 开始):
开始选取基准 base = 37,初始位置下表 low = 0 , high = 8 , 从high=8,开始如果R[8] < base , 将high位置中的内容写入到R[low]中, 将high位置空出来, low = low +1 ;
从low开始探测,由于low=1 , R[low] > base ,所以将R[low]写入到R[high] , high = high -1 ;
检测到low < high ,所以第一趟快速排序仍需继续:
此时low=1,high=7,因为 R[high] < base ,所以将 R[high] 写入到到R[low]中,low = low + 1;
从low开始探测,low = 2 , R[low] >base ,所以讲R[low]写入到R[high],high=high-1;
继续检测到 low 小于high
此时low=2,high=6,同理R[high] < base ,将R[high] 写入到R[low]中,low=low+1;
从low继续探测,low = 3 , high=6 , R[low] > base , 将R[low]写入到R[high]中,high = high-1;
继续探测到low小于high
此时low=3,high=5,同理R[high] < base,将R[high]写入到R[low]中,low = low +1;
从low继续探测,low = 4,high=5,由于R[low] > base , 将R[low]写入到R[high]中,high = high -1 ;
此时探测到low == high == 4 ;该位置即是base所在的位置,将base写入到该位置中.
然后再对子序列Rs1 = {12,9,7,5} 和 Rs2={461,42,38,40}做一趟快速排序,直到Rsi中只有一个元素,或没有元素。
private static boolean isEmpty(int[] n) { return n == null || n.length == 0; } //////////////////////////////////////////////////////** * 快速排序算法思想——挖坑填数方法: * * @param n 待排序的数组 */publicstaticvoid quickSort(int[] n) { if (isEmpty(n)) return; quickSort(n, 0, n.length - 1); } publicstaticvoid quickSort(int[] n, int l, int h) { if (isEmpty(n)) return; if (l < h) { int pivot = partion(n, l, h); quickSort(n, l, pivot - 1); quickSort(n, pivot + 1, h); } } privatestaticint partion(int[] n, int start, int end) { int tmp = n[start]; while (start < end) { while (n[end] >= tmp && start < end) end--; if (start < end) { n[start++] = n[end]; } while (n[start] < tmp && start < end) start++; if (start < end) { n[end--] = n[start]; } } n[start] = tmp; return start; }
原文:http://www.cnblogs.com/yunger/p/7514133.html
内容总结
以上是互联网集市为您收集整理的排序算法全部内容,希望文章能够帮你解决排序算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。