排序算法之交换排序

浏览数：16 / 时间：2015年06月08日

首先，上脑图。

1、为什么要学习排序算法？

这是算法学习的基础，经典的排序算法有着很广泛的用途，一遍遍的被人所使用。而且，在面试找工作的时候，数据结构中的排序算法，也是一个很重要的基本功，经常会被用人单位拿来出题目。

2、如何学习排序算法？

第一步是理解排序算法的原理，这也是最重要的一步。

第二步就是看经典的算法实现，抠细节一个个理解原理到实现经过了哪些变化。

第三部是用纸把算法实现抄一遍，这个时候会发掘出认识和实际的偏差。

第四步是把算法默写出来，这也是很重要的一步，类似于牛吃了食物之后的反刍过程，会进一步加深对于算法的理解。

第五步，将算法代码用各种语言实现出来，并且体会不同语言实现起来的差异。

第六步就是做总结和分享，进一步加深印象，并有助于以后再回过头来看。

3、交换排序算法原理分析

比较典型的交换排序算法有两个，分别是冒泡排序和快速排序。冒泡排序，主要的思想为每次排好一个最大的（或最小的）数，然后在剩下的数据里面继续这个排序最大数（最小数）的过程，直到所有数据都有序为止。冒泡排序的时间复杂度是O(n²)。冒泡排序的特点是，实现简单，但是效率低下。

快速排序，主要的思想为每次挑选一个数，和剩下的数依次做比较，比这个数要大的数据放在这个数据的后面位置，比这个数小的放在前面的位置。一轮过后，就找到这个数在全体数据中的位置。接下来，用同样的方法分别递归这个数的左边和右边。最后得到一个有序数组。快速排序的时间复杂度为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 }