1、基本思想：二分法插入排序的思想和直接插入一样，只是找合适的插入位置的方式不同，这里是按二分法找到合适的位置，可以减少比较的次数。
2、实例
3、java实现
package BinaryInsertSort; public class BinaryInsertSort { public static void main(String[] args) { int[] a = { 49, 38, 65, 97, 176, 213, 227, 49, 78, 34, 12, 164, 11, 18, 1 }; System.out.println("排序之前："); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } // 二分插入排序 sort(a); System.out.println(); System.out.println("排序之后："); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } } private static void sort(int[] a) { for (int i = 0; i < a.length; i++) { int temp = a[i]; int left = 0; int right = i - 1; int mid = 0; while (left <= right) { mid = (left + right) / 2; if (temp < a[mid]) { right = mid - 1; } else { left = mid + 1; } } for (int j = i - 1; j >= left; j--) { a[j + 1] = a[j]; } if (left != i) { a[left] = temp; } } } }(3)希尔排序
1、基本思想：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2
package ShellSort; public class ShellSort { public static void main(String[] args) { int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1 }; System.out.println("排序之前："); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } // 希尔排序 int d = a.length; while (true) { d = d / 2; for (int x = 0; x < d; x++) { for (int i = x + d; i < a.length; i = i + d) { int temp = a[i]; int j; for (j = i - d; j >= 0 && a[j] > temp; j = j - d) { a[j + d] = a[j]; } a[j + d] = temp; } } if (d == 1) { break; } } System.out.println(); System.out.println("排序之后："); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } } } ② 选择排序•思想：每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置，直到全部排完。
•关键问题：在剩余的待排序记录序列中找到最小关键码记录。
•方法：
–直接选择排序
–堆排序
(1)直接选择排序
1、基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
2、实例
3、java实现
package DirectSelectSort; public class DirectSelectSort { public static void main(String[] args) { int[] a = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 1, 8 }; System.out.println("排序之前："); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } // 直接选择排序 for (int i = 0; i < a.length; i++) { int min = a[i]; int n = i; // 最小数的索引 for (int j = i + 1; j < a.length; j++) { if (a[j] < min) { // 找出最小的数 min = a[j]; n = j; } } a[n] = a[i]; a[i] = min; } System.out.println(); System.out.println("排序之后："); for (int i = 0; i < a.length; i++) { System.out.print(a[i] + " "); } } }(2)堆排序
1、基本思想：
堆排序是一种树形选择排序，是对直接选择排序的有效改进。