几种常见排序算法(Java实现)

Summary by Leon Liu 排序算法 冒泡排序: 思想: n个数,将第一个和第二个进行比较,将大的放在第二个位置,再将第二个和第三比较,大的放在第三个位置,依次向后比较,比较n-1次,将最大的放在最后(n的位置),然后再从第一个开始比较,比较n-2次,这次把最大的放到第n-1个位置,然后再来回比较.遵循第i次遍历就从第一个数开始比较n-i次,将最后的值放在第n-i+1的位置. java代码实现: // 冒泡排序 public class BubbleSort { public static void sort(Comparable[] data) { // 数组长度 int len = data.length; for (int i = 0; i < len - 1; i++) { // 临时变量 Comparable temp = null; // 交换标志,false表示未交换 boolean isExchanged = false; for (int j = len - 1; j > i; j--) { // 如果data[j]小于data[j - 1],交换 if (data[j].compareTo(data[j - 1]) < 0) { temp = data[j]; data[j] = data[j - 1]; data[j - 1] = temp; // 发生了交换,故将交换标志置为真 isExchanged = true; }// end if }// end for // 本趟排序未发生交换,提前终止算法,提高效率 if (!isExchanged) { break; }// end if }// end for }// end sort public static void main(String[] args) { // 在JDK1.5版本以上,基本数据类型可以自动装箱 // int,double等基本类型的包装类已实现了Comparable接口 Comparable[] c = { 4, 9, 23, 1, 45, 27, 5, 2 }; sort(c); System.out.println("冒泡排序后: "); for(int i = 0; i s[i + 1]) { int temp; temp = s[i]; s[i] = s[i + 1]; s[i + 1] = temp; } } } for (int i = 0; i < s.length; i++) { System.out.println(s[i]); } } } 快速排序: 思想: 基于冒泡排序,取第一个作为关键值a,用a与后面开始往前比较,遇到比a小的则交换,依然乘此关键值为a,再用a与第一个数开始向后比较,遇到比a大的则交换,最终的关键值将依然是最初的第一个元素的值,用此值将此无序序列分成两部分,比它小的都在它前面,大的都在后面,然后用递归将前面和后面的分别用快速排序进行处理,得到最终的有序序列. java代码实现: public class QuickSort { public static void main(String[] args) { // int [] arry={49, 38, 65, 97, 76, 13, 27}; int[] arry = { 27, 38, 65, 97, 76, 48, 49 }; // 程序还有问题.比如当数据为49,38, 65, 97, 76, 13, 27,12,11 // 的时候,第一次就把最小一位放到第一位,,而出现问题 QuickSort.method2(arry); // Arrays.sort(arry, 0, arry.length); for (int i = 0; i < arry.length; i++) { System.out.println("结果:" + arry[i]); } } /** * 快速排序* @param arry */ public static void method2(int[] array) { // 1)设置两个变量I、J,排序开始的时候:I=0,J=N-1; int i = 0; int j = array.length - 1; // 获取数组最后一位 // 2)以第一个数组元素作为关键数据,赋值给key,即 key=A[0]; int k = array[0]; // 获取数组第一位 int f = 0; boolean check = false; int x = 0; while (i != j) { // 3)从J开始向前搜索,即由后开始向前搜索(J=J-1),找到第一个小于key 的值A[J],并与key交换; while (array[j] > k) { j--; } System.out.println("i0: "+ i + "; "+ "j0: "+ j + "; "+ "k0: " + k + "; f0: " + f); int temp = k; k = array[j]; array[j] = temp; // [49, 38, 65, 97, 76, 13, 49] //[27, 38, 65, 97, 76, 13, 49] // [27, 38, 49, 97, 76, 13, 65] //[27, 38, 49, 97, 76, 49, 65] // [27, 38, 13, 97, 76, 49, 65] //[27, 38, 13, 49, 76, 97, 65] // [27, 38, 13, 49, 76, 97, 65] // 4)从I开始向后搜索,即由前开始向后搜索(I=I+1),找到第一个大于key 的A[I],与key交换; while (array[i] < k) { i++; } System.out.println("i1: "+ i + "; "+ "j1: "+ j + "; "+ "k1: " + k + "; f1: " + f); int temp1 = k; k = array[i]; array[i] = temp1; System.out.println("i2: "+ i + "; "+ "j2: "+ j + "; "+ "k2: " + k + "; f2: " + f); for (int a = 0; a < array.length; a++) { System.out.print(array[a] + ","); } System.out.println(); // [27, 38, 65, 97, 76, 13, 49] //[27, 38, 49, 97, 76, 13, 49] // [27, 38, 49, 97, 76, 13, 65] //[27, 38, 13, 97, 76, 49, 65] // [27, 38, 13, 49, 76, 49, 65] //[27, 38, 13, 49, 76, 97, 65] System.out.println(array[i] + " " + array[j]); if (array[i] == array[j]) { x++; if (x > (array.length / 2 + 1)) { check = true; } } if (i == j || check) { k = array[0]; // 获取数组第一位 if (i == j && i == 0) { k = array[1]; } i = 0; j = array.length - 1; // 获取数组最后一位 check = false; x = 0; if (f > (array.length / 2 + 1)) { k = array[j]; } if (f == array.length) { break; } f++; }// [27, 38, 13, 49, 76, 97, 65] //[13, 27, 38, 49, 76, 97, 65] } // } } } } 插入排序(直接插入排序): 思想: 先将无序序列中的第一个值去除作为关键值,然后将其放入有序序列(即作为新序列的第一个值),然后取第二个值作为关键值,将关键值放入有序序列,并与第一个值进行比较,若小于第一个值,则将这个关键值插入到第一个值前面(交换),后面依次取值然后和前面的有序序列中的值进行比较,插入到合适位置 java代码实现: public class InsertSort { public static void sort(Comparable[] data) { // 数组长度 int len = data.length; // 从下标为1开始依次插入 for (int i = 1; i < len; i++) { // 当前待插入的数据 Comparable currentData = data[i]; int temp = i; while(temp > 0 && data[temp - 1].compareTo(currentData) > 0) { // 向右移动 data[temp] = data[temp - 1]; temp--; } // end while data[temp] = currentData; }// end for }// end sort public static void main(String[] args) { // 在JDK1.5版本以上,基本数据类型可以自动装箱 // int,double等基本类型的包装类已实现了Comparable接口 Comparable[] c = { 4, 9, 23, 1, 45, 27, 5, 2 }; sort(c); System.out.println("插入排序后: "); for(int i = 0; i arr[j]) min = j; } if (min != i) { temp = arr[min]; arr[min] = arr[i]; arr[i] = temp; } } /*System.out.println("排序后的数组为:"); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); }*/ } }