一、选择排序
原理是每一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
示例代码如下：
public class StraightSelectSort { /** * 选择排序 * @param a */ public static void sort(int[] a) { int n=a.length; for(int i=0;i<n;i++) { int min=i; /** * 找到i后面最小的值 */ for(int j=i+1;j<n;j++) { if(a[j]<a[min]) min=j; } /* * 将i位置上的值与后面的最小值对换 */ changeData(a, i, min); } } //交换数据 private static void changeData(int[] a, int i, int min) { int temp; temp=a[i]; a[i]=a[min]; a[min]=temp; } }
二、插入排序
基本思想是每一步将一个待排序的元素，按照其关键码值的大小插入到已经排序的文件适当位置上，直到全部插入完为止。
示例代码：
/** * 插入排序 * @author Administrator * */ public class InsertSort { public static void sort(int[] a) { int n=a.length; /** * 对于0到n-1之间的每一个i,将a[i]与a[0]到a[i-1]中比它小的所有元素都依次有序交换 * 在i由左到右的过程中，它左侧的元素总是有序的 */ for(int i=1;i<n;i++) { for(int j=i;j>0 && (a[j]-a[j-1])<0;j--) { changeData(a, j, j-1); } } } //交换数据 private static void changeData(int[] a, int i, int min) { int temp; temp=a[i]; a[i]=a[min]; a[min]=temp; } }
三、希尔排序
希尔排序是插入排序的一种，也称为缩小增量排序，是直接插入排序算法的一种更高效的改进版本。基本思想是把记录按下标的一定增量分组，对每组使用直接插入算法排序，随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件就被分为一组，算法终止。
示例代码：
/** * 希尔排序 * @author Administrator * */ public class ShellSort { public static void sort(int[] a) { int d=a.length; //间距初始值设为数组长度 while(true) { for(int i=0;i<d;i++) for(int j=i;j+d<a.length;j=j+d) { if(a[j]>a[j+d]) { changeData(a, j, j+d); } } if(d==1) break; d--; } } //交换数据 private static void changeData(int[] a, int i, int min) { int temp; temp=a[i]; a[i]=a[min]; a[min]=temp; } }
四、快速排序
快速排序是对冒泡排序的一种改进，基本思想是：通过一趟排序将要排序的数据分割成独立的两个部分，其中一个部分的所有数据都比另外一个部分的所有数据都要小，然后在按照此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
/** * 快速排序 * @author Administrator * */ public class QuickSort { public static void sort (int []a) { sort(a,0,a.length-1); } private static void sort(int []a,int lo,int hi) { if(hi<=lo) return ; int j=partition(a,lo,hi); sort(a,lo,j-1); sort(a,j+1,hi); } static int partition(int s[], int lo, int hi) //返回调整后基准数的位置 { int i = lo, j = hi; int x = s[lo]; //s[lo]即s[i]就是第一个坑 while (i < j) { // 从右向左找小于x的数来填s[i] while(i < j && s[j] >= x) j--; if(i < j) { s[i] = s[j]; //将s[j]填到s[i]中，s[j]就形成了一个新的坑 i++; } // 从左向右找大于或等于x的数来填s[j] while(i < j && s[i] < x) i++; if(i < j) { s[j] = s[i]; //将s[i]填到s[j]中，s[i]就形成了一个新的坑 j--; } } //退出时，i等于j。将x填到这个坑中。 s[i] = x; return i; } /* private static int partition(int[] a, int lo, int hi) { int i=lo; int j=hi+1; int v=a[lo]; while(true) { while(a[++i]<v) { if(i==hi) break; } while(v<a[--j]) { if(j==lo) break; } if(i>=j) break; changeData(a, i, j); } changeData(a, lo, j); return j; } //交换数据 private static void changeData(int[] a, int i, int j) { int temp; temp=a[i]; a[i]=a[j]; a[j]=temp; }*/ }