排序算法之交换排序

首先,上脑图。

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 }

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。