首页 > 代码库 > 排序算法之交换排序
排序算法之交换排序
首先，上脑图。
1、为什么要学习排序算法？
这是算法学习的基础，经典的排序算法有着很广泛的用途，一遍遍的被人所使用。而且，在面试找工作的时候，数据结构中的排序算法，也是一个很重要的基本功，经常会被用人单位拿来出题目。
2、如何学习排序算法？
第一步是理解排序算法的原理，这也是最重要的一步。
第二步就是看经典的算法实现，抠细节一个个理解原理到实现经过了哪些变化。
第三部是用纸把算法实现抄一遍，这个时候会发掘出认识和实际的偏差。
第四步是把算法默写出来，这也是很重要的一步，类似于牛吃了食物之后的反刍过程，会进一步加深对于算法的理解。
第五步，将算法代码用各种语言实现出来，并且体会不同语言实现起来的差异。
第六步就是做总结和分享，进一步加深印象，并有助于以后再回过头来看。
3、交换排序算法原理分析
比较典型的交换排序算法有两个，分别是冒泡排序和快速排序。冒泡排序，主要的思想为每次排好一个最大的（或最小的）数，然后在剩下的数据里面继续这个排序最大数（最小数）的过程，直到所有数据都有序为止。冒泡排序的时间复杂度是O(n2)。冒泡排序的特点是，实现简单，但是效率低下。
快速排序，主要的思想为每次挑选一个数，和剩下的数依次做比较，比这个数要大的数据放在这个数据的后面位置，比这个数小的放在前面的位置。一轮过后，就找到这个数在全体数据中的位置。接下来，用同样的方法分别递归这个数的左边和右边。最后得到一个有序数组。快速排序的时间复杂度为O（n logn）。快速排序的特点是，实现复杂，时间复杂度低。
最后，上代码，先是冒泡排序：
1 public class Maopao { 2 3 /** 4 * @param args 5 */ 6 public static void main(String[] args) { 7 // TODO Auto-generated method stub 8 int num[]={10,9,8,7,6,5,4,3,2,1}; 9 new Maopao().maopao(num);10 for(int i=0;i<num.length;i++){11 System.out.print(num[i]+",");12 }13 }14 public void maopao(int num[]){15 int i,j,temp;16 for(i=0;i<num.length-1;i++){17 for(j=0;j<num.length-1-i;j++){18 if(num[j]>num[j+1]){19 temp=num[j];20 num[j]=num[j+1];21 num[j+1]=temp;22 }23 }24 }25 }26 27 }
然后是快排：
1 public class Qsort { 2 3 /** 4 * @param args 5 */ 6 public static void main(String[] args) { 7 // TODO Auto-generated method stub 8 int num[]={0,10,9,8,7,6,5,4,3,2,1}; 9 new Qsort().Qsot(num);10 for(int i=1;i<num.length;i++){11 System.out.print(num[i]+",");12 }13 }14 int partition(int num[],int low,int high){15 num[0]=num[low];16 int p=num[low];17 while(low<high){18 while(low<high && num[high]>=p)high--;19 num[low]=num[high];20 while(low<high && num[low]<=p)low++;21 num[high]=num[low];22 }23 num[low]=num[0];24 return low;25 }26 public void QuickSort(int num[],int low,int high){27 if(low<high){28 int p = partition(num,low,high);29 QuickSort(num,p+1,high);30 QuickSort(num,low,p-1);31 }32 }33 public void Qsot(int num[]){34 QuickSort(num,1,num.length-1);35 }36 }
排序算法之交换排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。