【简单排序算法】：简单选择排序、直接插入排序和冒泡排序
简单选择排序：
原理：设所排序序列的记录个数为n。i取1,2,…,n-1,每次从所有n-i+1个记录（Ri,Ri+1,…,Rn）中找出最小的记录，与第i个记录交换。执行n-1趟 后就完成了记录序列的排序。性能：最好、最坏和平均时间复杂度均为O(n2)，不稳定排序算法。
JAVA实现：
1 //简单选择排序 2 public static int[] simple_choose_sort(int[] source) { 3 4 int length = source.length; 5 int small; 6 7 for(int i=0;i<length-1;i++) {//要进行length-1趟排序 8 9 small = i; //每趟开始时假设第一个元素最小 10 11 for(int j=i+1;j<length;j++) {//对于i后面的每个元素 12 13 if(source[small]>source[j]) { 14 15 small = j;//如果有元素比目前最小的元素还小，就记下它的下标 16 17 } 18 } 19 swap(source,i,small);//交换第一个元素和最小的元素 20 } 21 return source; 22 }
直接插入排序：
原理：将序列中第一个元素作为一个有序序列，将剩下的n-1个元素按关键字大小一次插入该数列，每次插入一个数据后保持该序列依然有序，n-1趟就可以数组排序完成。
性能：最好的时间复杂度为n，最坏为n2，该算法为稳定算法。
JAVA实现：
1 //直接插入排序 2 private static int[] direct_insert_sort(int[] source) { 3 4 int length = source.length;//数组的长度 5 6 for(int i=1;i<length;i++) {//执行length-1趟 7 8 int j = i; 9 int compare = source[i];//先保存当前元素的信息 10 11 while(j>0&&source[j-1]>compare) {//source[j-1]>compare为稳定算法，source[j-1]>=compare为不稳定 12 13 source[j] = source[j-1];//从后往前比较前面的i个元素，如果compare比前一个小，就将该元素后移 14 j--; 15 } 16 source[j] = compare;//将插入元素存入找到的插入位置 17 } 18 return source; 19 }
冒泡排序算法：
原理：最多比较n-1趟，第1趟是从第1个到第n个，相邻的两个元素比较，如果前面的小于后面的，就交换位置，第二趟从第2个到第n个，重复第一趟的工作。如果某一趟没有交换元素，那么就可以断定已经排序完成
性能：最小时间复杂度n，最大为n2,该算法为稳定算法
JAVA实现：
//冒泡排序算法 private static int[] bubble_up_sort(int[] source){ int length = source.length;//数组的长度 int j,last; int i=length-1; while(i>0) { last = 0;//last设置为0，最为一个标志，如果下面的for循环没有改变last,这i设置为0，排序完毕 for(j=0;j<i;j++) { if(source[j+1]<source[j]) { swap(source,j+1,j);//交换两个数 last = j;//记录最后一次交换数据的位置，last后面的元素已经有序，下次就不用去比较了 } } i=last;//如果某一趟中没有交换数据，则last为0，通知i被设置为0，排序完毕 } return source; }
完整的工程代码：
1 /** 2 * This program shows all kinds of sort-algorithm 3 * @author hewenwu 4 * @version 1.0 2014/4/15 5 * */ 6 7 public class Algorithm { 8 9 10 11 public static void main(String[] args) { 12 13 int[] source = new int[20]; 14 15 //获取随机数组 16 int i=0; 17 while(i<20) { 18 source[i] = (int) (Math.random()*100); 19 i++; 20 } 21 22 System.out.println("原始数组为："); 23 print_array(source); 24 25 System.out.println ("简单选择排序后的数组:"); 26 print_array(simple_choose_sort(source)); 27 28 System.out.println ("直接插入排序后的数组:"); 29 print_array(direct_insert_sort(source)); 30 31 System.out.println ("冒泡排序后的数组:"); 32 print_array(bubble_up_sort(source)); 33 34 } 35 36 //简单选择排序 37 public static int[] simple_choose_sort(int[] source) { 38 39 int length = source.length; 40 int small; 41 42 for(int i=0;i<length-1;i++) {//要进行length-1趟排序 43 44 small = i; //每趟开始时假设第一个元素最小 45 46 for(int j=i+1;j<length;j++) {//对于i后面的每个元素 47 48 if(source[small]>source[j]) { 49 50 small = j;//如果有元素比目前最小的元素还小，就记下它的下标 51 52 } 53 } 54 swap(source,i,small);//交换第一个元素和最小的元素 55 } 56 return source; 57 } 58 59 //直接插入排序 60 private static int[] direct_insert_sort(int[] source) { 61 62 int length = source.length;//数组的长度 63 64 for(int i=1;i<length;i++) {//执行length-1趟 65 66 int j = i; 67 int compare = source[i];//先保存当前元素的信息 68 69 while(j>0&&source[j-1]>compare) {//source[j-1]>compare为稳定算法，source[j-1]>=compare为不稳定 70 71 source[j] = source[j-1];//从后往前比较前面的i个元素，如果compare比前一个小，就将该元素后移 72 j--; 73 } 74 source[j] = compare;//将插入元素存入找到的插入位置 75 } 76 return source; 77 } 78 79 //冒泡排序算法 80 private static int[] bubble_up_sort(int[] source){ 81 82 int length = source.length;//数组的长度 83 int j,last; 84 int i=length-1; 85 86 while(i>0) { 87 88 last = 0;//last设置为0，最为一个标志，如果下面的for循环没有改变last,这i设置为0，排序完毕 89 90 for(j=0;j<i;j++) { 91 92 if(source[j+1]<source[j]) { 93 94 swap(source,j+1,j);//交换两个数 95 96 last = j;//记录最后一次交换数据的位置，last后面的元素已经有序，下次就不用去比较了 97 } 98 } 99 i=last;//如果某一趟中没有交换数据，则last为0，通知i被设置为0，排序完毕 100 } 101 return source; 102 103 } 104 105 106 //交换两个整数 107 private static void swap(int[] source, int i, int j) { 108 109 int temp = source[i]; 110 source[i] = source[j]; 111 source[j] = temp; 112 } 113 114 //打印数组 115 private static void print_array(int[] source) { 116 117 for(int i=0;i<source.length;i++) { 118 119 System.out.print(source[i]+"-"); 120 121 } 122 System.out.println(); 123 } 124 125 }
【简单排序算法】：简单选择排序、直接插入排序和冒泡排序,布布扣,bubuko.com
原文：http://www.cnblogs.com/hewenwu/p/3667434.html