一、前言

在实现数组元素排序时，常用的有：快速排序法、选择排序法、冒泡排序、插入排序(文档示例参见相关PPT教程)。其中快速排序法被认为是当今最好的排序法之一，java提供的数组排序实现（Arrays.sort(int[] a)）就是基于快速排序法（相关参见视频教程下载）,对于排序算法时间复杂度情况如下

时间复杂度计算O（n）- 最坏情况下的时间复杂度，log2(n) - 基于对数组的二分查找算法的折算（最坏情况遍历数组大小n/2范围）@b@@b@排序法   平均时间  @b@冒泡     O(n*n)  @b@交换     O(n*n)   @b@选择     O(n*n)  @b@插入     O(n*n)  @b@ @b@快速     log2(n)*n@b@归并     log2(n)*n@b@堆       log2(n)*n@b@希尔     n的1.2次幂  - 接近线性排序效率

1.快速排序法,实现思路是将一个大的数组的排序问题，分解成2个小的数组排序的排序，然后将每个小的数组再继续拆分更小的2个数组，这样一直递归分解下去，直到数组大小最大为2为止，示例代码如下：

public class QuickSort {@b@    public  static  int[]  quickSort(int[] arr,int left,int right){@b@        int x;@b@        if(left<right){@b@            int s=arr[left];@b@            int i=left;@b@            int j=right+1;@b@            while(true){@b@                while(i+1<arr.length&&arr[++i]<s);//向右找到大于s值得索引@b@                while(j-1>-1&&arr[--j]>s);//向左找到小于s值得索引@b@                if(i>=j){//如何i>=j，退出循环@b@                    break;@b@                }else{@b@                    x=arr[i];//交换i和j位置的元素@b@                    arr[i]=arr[j];@b@                    arr[j]=x;@b@                }@b@             @b@            }@b@        arr[left]=arr[j];@b@        arr[j]=s;@b@        quickSort(arr,left,j-1);//对左边进行递归@b@        quickSort(arr,j+1,right);//对右边进行递归         @b@        }@b@        return arr;@b@}@b@    public static void main(String[] args) {@b@        int[] ints={2,33,44,6,77,9,11,3,8,99,155,35,98,124};@b@        quickSort(ints,0,10);@b@        System.out.println(Arrays.toString(ints));@b@@b@    }@b@@b@}@b@//输出:[2, 3, 6, 8, 9, 11, 33, 44, 77, 99, 155, 35, 98, 124]

效果如下图所示

直接利用提供排序方法，如下：

int[] ints={2,33,44,6,77,9,11,3,8,99,155,35,98,124};@b@ @b@Arrays.sort(ints);  //进行排序 @b@@b@System.out.println(Arrays.toString(a));@b@@b@//输出:[2, 3, 6, 8, 9, 11, 33, 35, 44, 77, 98, 99, 124, 155]

2.选择排序法 - 循环n次，每次排出最大或最小者与剩余最高位者置换，示例代码如下：

int[] ints={2,33,44,6,77,9,11,3,8,99,155,35,98,124};@b@int maxIndex=0;@b@for(int i=ints.length-1;i>-1;i--){@b@     int max=ints[0];@b@     for(int j=0;j<=i;j++){@b@           if(max<=ints[j]){@b@              max=ints[j];@b@              maxIndex=j;@b@            } @b@      }@b@      int _v=ints[i];@b@      ints[i]=max;@b@      ints[maxIndex]=_v;@b@}@b@System.out.println(Arrays.toString(ints));@b@//输出:[2, 3, 6, 8, 9, 11, 33, 35, 44, 77, 98, 99, 124, 155]

效果如下图所示

3.冒泡排序法 - 迭代n次，每次将剩余位置依次排序置换（正序或倒序）。示例代码：

int[] ints={2,33,44,6,77,9,11,3,8,99,155,35,98,124};@b@for(int i=0;i<ints.length;i++){@b@   for(int j=0;j<ints.length-1-i;j++){@b@       int _v=ints[j+1];@b@       if(ints[j]>ints[j+1]){@b@          ints[j+1]=ints[j];@b@          ints[j]=_v;@b@       }     @b@   }@b@}@b@System.out.println(Arrays.toString(ints));@b@@b@//输出:[2, 3, 6, 8, 9, 11, 33, 35, 44, 77, 98, 99, 124, 155]

效果如下图所示

4.插入排序法，从第2位置遍历，将之前的依次排序置换，示例代码如下：

 int[] ints={2,33,44,6,77,9,11,3,8,99,155,35,98,124};@b@ for(int i=1;i<ints.length;i++){ @b@     int tmp=ints[i];@b@     int j=i-1;@b@     while(j>-1){@b@        if(ints[j]>ints[j+1]){@b@           ints[j+1]=ints[j];@b@           ints[j]=tmp;@b@        }@b@        tmp=ints[j];@b@        j--;@b@      }@b@}@b@System.out.println(Arrays.toString(ints));@b@@b@//输出:[2, 3, 6, 8, 9, 11, 33, 35, 44, 77, 98, 99, 124, 155]

��