排序算法（冒泡、插入、选择、希尔、桶）

一、冒泡排序

基本思想是:两两比较相邻记录的关键字,如果反序则交换

基本代码如下：

int[] arr={5,6,8,9,7,11}; for (int i = 0,t; i <arr.length-1 ; i++) { for (int j = 0; j <arr.length-1-i ; j++) { if (arr[j]>arr[j+1]) { t=arr[j]; arr[j]=arr[j+1]; arr[j+1]=t; } } } for (int i :arr) { System.out.println(i); }

二、插入排序

基本思想是:通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

基本代码如下：

int[] arr={5,6,8,9,7,11}; for (int i = 0,t,j; i < arr.length; i++) { t=arr[i]; for (j=i-1;j>=0 && arr[j]>t ; j--) { arr[j+1]=arr[j]; } arr[j+1] =t; } for (int i :arr) { System.out.println(i); }

三、简单选择排序 首先选出数组中最小的元素，将它与数组中第1个元素交换，然后找出次小的元素，并将它与数组中第2个元素交换按照这种方法一直进行下去，直到整个数组排完序

int[] arr={5,6,8,9,7,11}; for (int i = 0,maxIx,maxValIx,t; i <arr.length-1 ; i++) { maxValIx=0; maxIx = arr.length-1-i; for (int j = 1; j <=arr.length-1 ; j++) { if(arr[maxValIx]<arr[j]){ maxValIx = j; } } if(maxIx != maxValIx){ t = arr[maxIx]; arr[maxIx] = arr[maxValIx]; arr[maxValIx] = t; } } for (int i :arr) { System.out.println(i); }

四、希尔排序 先将整个待排元素序列分割成若干子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序（增量为1）。

基本代码如下：

int[] arr={89,56,4,12,87,36,54,21,98,55,12,14,19,52,26,36,45,48,49,2,6,3,43}; int step=arr.length,t; while((step=step/2)>2){ for (int i = 0; i+step <arr.length ; i++) { if(arr[i]>arr[i+step]){ t=arr[i]; arr[i]=arr[step]; arr[step]=t; } } } for(int i :arr){ System.out.print(i+"\t"); } System.out.println(); for (int i = 0,j; i <arr.length ; i++) { t=arr[i]; for ( j = i-1; j >=0 && arr[j]>t ; j--) { arr[j+1]=arr[j]; } arr[j+1] = t; } for (int i:arr){ System.out.print(i+"\t"); }

五、桶排序 它假设输入数据服从均匀分布，我们将数据分别放入到 n 个桶内，先对桶内数据进行排序，然后遍历桶依次取出桶中的元素即可完成排序。

原理图： 例如输入数据：21，8，6，11，36，50，27，42，0，12。 然后分别放入对应的桶内排序，最后依次遍历桶取出元素即可完成排序。

基本代码如下：

int[] arr={89,56,4,12,87,36,54,21,98,55,12,14,19,52,26,36,45,48,49,2,6,3,43}; final int U =10; int[][] bucket = new int [U][arr.length]; int[]ixs = new int [U]; for (int i = 1,count,t;; i*=10) { count = 0; for (int j = 0; j <arr.length ; j++) { count = (t=arr[j]/i)>=1 ? ++count : count; bucket[t%=U][ixs[t]++]=arr[j]; } if(count==0)break; for (int j = 0,ix=0; j <bucket.length ; j++) { for (int k = 0; k < ixs[j]; k++) { arr[ix++] = bucket[j][k]; } } for (int j = 0; j <ixs.length ; j++) { ixs[j]=0; } } for (int i:arr) { System.out.print(i + "\t"); }