排序应用
应用广泛：一旦建立数据库后，就可能根据某些需求对它进行排序。比如，对员工按工资排序，对学生按年级排序，对商品按价格排序，对城市按人口增长率排序，对国家按GDP排序，以及对恒星按大小排序。
重要性：由于排序非常重要而且可能非常耗时，所以它已经成为计算机科学中一个被广泛研究的课题。
排序的稳定性：如果具有相同关键字的数据项，经过排序它们的顺序保持不变，这样的排序就是稳定的。
冒泡排序
概述：冒泡排序算法最简单，但效率最低。
算法：1和2比较，2和3比较，3和4比较...，把最大的逐步冒泡到最顶端。
效率：
比较次数：
假如一共有5个人比较高低，一共要比较4轮，第一轮要比较4次，第二轮比较3次，第三轮比较2次，第四轮比较1次，总共需要比较4+3+2+1次。
这是一个有序数列，公式为(N-1+1)*(N-1)/2，即N*(N-1)/2，忽略1,N2/2
交换次数：
如果数字是随机的，大概有一半数据需要交换，即N2/4
交换和比较次数都和N2成正比，所以用大O表示法，冒泡排序表示为O(N2)
无论何时，只要看到双层循环，就可以怀疑这个算法的运行时间是O(N2)。外层循环N次，内部循环每次执行N次或几分之N次，这就意味着将大约需要N2次基本操作。
int arrLength = arr.length; int temp = 0; // 假设一共有5个人比较个子高低 // i的取值为最后一个需要比较大小的元素 // 第一个轮回最后一次比较的两个数的第二个数的下标是4 // 第二个轮回最后一次比较的两个数的第二个数的下标是3 // 第三个轮回最后一次比较的两个数的第二个数的下标是2 // 第四个轮回最后一次比较的两个数的第二个数的下标是1 for (int i = arrLength - 1; i > 0; i--) { // 每一个轮回总是1和2比较，2和3比较，3和4比较...，所以j=0 // 因为后面是j和j+1比较，所以j的最大取值范围是这一轮回最后一次比较时两个数的第一个数，也就是j < i for (int j = 0; j < i; j++) { if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } }
package MyTest; import java.util.Arrays; import java.util.Random; public class OrderArray { public static void main(String[] args) { int[] arr = new int[]{100, 99, 56, 78, 50}; //fill(arr); print(arr); println(); sort(arr); print(arr); } private static void println() { System.out.println(); } static void sort(int[] arr) { int arrLength = arr.length; int temp = 0; // 假设一共有5个人比较个子高低 // i的取值为最后一个需要比较大小的元素 // 第一个轮回最后一次比较的两个数的第二个数的下标是4 // 第二个轮回最后一次比较的两个数的第二个数的下标是3 // 第三个轮回最后一次比较的两个数的第二个数的下标是2 // 第四个轮回最后一次比较的两个数的第二个数的下标是1 for (int i = arrLength - 1; i > 0; i--) { // 每一个轮回总是1和2比较，2和3比较，3和4比较...，所以j=0 // 因为后面是j和j+1比较，所以j的最大取值范围是这一轮回最后一次比较时两个数的第一个数，也就是j < i for (int j = 0; j < i; j++) { if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } static void fill(int[] arr) { Random random = new Random(); for (int i = 0; i < 100; i++) { int num = random.nextInt(100); arr[i] = num; } } static void print(int[] arr) { for (int i = 0; i < 5; i++) { System.out.print(arr[i] + " | "); } } }
选择排序
效率：选择排序改进了冒泡排序，将交换次数从O(N2)减少到O(N)，但比较次数仍为O(N2)。
算法：从内部循环的一个轮回中选择出最小值并记录其下标值，当内部循环结束后，把这个最小值和最左边的数交换位置。
int arrLength = arr.length; int temp = 0; int min = 0; // 假如有5个人需要按照个子高低排序 // 第一轮假设下标0的元素是最小的 // 第二轮假设下标1的元素是最小的 // 第三轮假设下标2的元素是最小的 // 第四轮假设下标3的元素是最小的，这是最后一轮比较，这次比较只有两个数，下标为3的数是这个数组倒数第2个数，所以i < arrLength-1 for (int i = 0; i < arrLength - 1; i++) { min = i; // 把最小的数和第2个数、第3个数、第4个数依次比较... for (int j = i + 1; j < arrLength; j++) { // 如果还有一个数a比这个数小，就把数a的下标记录下来 if (arr[min] > arr[j]) { min = j; } } temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; }
package MyTest; import java.util.Arrays; import java.util.Random; public class OrderArray { public static void main(String[] args) { int[] arr = new int[]{65, 17, 65, 34, 16, 52, 88, 28, 71, 18}; //fill(arr); print(arr); println(); sort(arr); print(arr); } private static void println() { System.out.println(); } static void sort(int[] arr) { int arrLength = arr.length; int temp = 0; int min = 0; // 假如有5个人需要按照个子高低排序 // 第一轮假设下标0的元素是最小的 // 第二轮假设下标1的元素是最小的 // 第三轮假设下标2的元素是最小的 // 第四轮假设下标3的元素是最小的，这是最后一轮比较，这次比较只有两个数，下标为3的数是这个数组倒数第2个数，所以i < arrLength-1 for (int i = 0; i < arrLength - 1; i++) { min = i; // 把最小的数和第2个数、第3个数、第4个数依次比较... for (int j = i + 1; j < arrLength; j++) { // 如果还有一个数a比这个数小，就把数a的下标记录下来 if (arr[min] > arr[j]) { min = j; } } temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; } } static void fill(int[] arr) { Random random = new Random(); for (int i = 0; i < 10; i++) { int num = random.nextInt(100); arr[i] = num; } } static void print(int[] arr) { for (int i = 0; i < 10; i++) { System.out.print(arr[i] + " | "); } } }
插入排序
效率：
插入排序仍需要O(N2)的时间。
比较次数：在第一轮中，比较1次；第二轮中，最多比较2次；第三轮中，最多比较3次...最后一轮，比较N-1次，即1+2+3+...+N-1，也就是N*(N-1)/2，但每一轮平均比较次数是最多比较次数的二分之一，所以平均比较次数是N*(N-1)/4，即N2/4。
复制次数：复制的次数大约等于比较的次数。但复制和交换不同，复制只一步操作，交换要三步操作。
比较：如果是随机数据，这个算法比冒泡排序快一倍，因为冒泡比较次数是N2/2，它的比较次数是N2/4，冒泡的交换次数是N2/4，它的复制次数也是N2/4，并且复制比交换还快；比选择排序略快，因为选择排序的比较次数是N2/2，它的比较次数是N2/4，选择排序交换N次，但它是复制，不是交换。
但如果是逆序数据，每次比较和移动都会执行，所以它并不比冒泡排序快。
应用：对于小规模文件以及基本有序的文件，插入排序能比快速排序更为有效。
算法：插入排序从排序过程的中间开始描述，更容易理解。
假如中部有一个元素是标记元素，那么它左边的元素从低到高都已经排好序了，即局部有序，它以及它右边的元素还没有排好序。
先把标记元素缓存一份。
现在把标记元素和局部有序部分里紧挨着它的元素比较，如果标记元素大，说明标记元素大于局部有序部分所有的元素,什么也不需要做；如果标记元素小，把与之比较的元素复制到下一个位置，接着把标记元素和有序部分倒数第二个元素比较......
int arrLength = arr.length; int temp = 0; // 假如有5个人需要按照个子高低排序 // 第一轮有序部分是下标为1的元素的左边是局部有序部分 // 第二轮有序部分是下标为2的元素的左边是局部有序部分 // 第三轮有序部分是下标为3的元素的左边是局部有序部分 // 第四轮有序部分是下标为4的元素的左边是局部有序部分 for (int i = 1; i < arrLength; i++) { // 把标记元素缓存起来 temp = arr[i]; int j = i; for (; j > 0 && temp < arr[j - 1]; j--) { // 如果缓存起来的数小于和它比较的数a，数a移动到下一个位置 arr[j] = arr[j - 1]; } // 两种情况需要把缓存起来的数复制回原数组 // 1、缓存起来的数大于和它比较的数 // 2、和它比较的数的下标为0的时候，因为下标为0的数已经和它比较过并且此时已经被复制到了下标为1处，下标为0的位置就是专门留给它的 arr[j] = temp; }
package MyTest; import java.util.Arrays; import java.util.Random; public class OrderArray { public static void main(String[] args) { int[] arr = new int[100]; fill(arr); print(arr); println(); sort(arr); print(arr); } private static void println() { System.out.println(); } static void sort(int[] arr) { int arrLength = arr.length; int temp = 0; // 假如有5个人需要按照个子高低排序 // 第一轮有序部分是下标为1的元素的左边是局部有序部分 // 第二轮有序部分是下标为2的元素的左边是局部有序部分 // 第三轮有序部分是下标为3的元素的左边是局部有序部分 // 第四轮有序部分是下标为4的元素的左边是局部有序部分 for (int i = 1; i < arrLength; i++) { // 把标记元素缓存起来 temp = arr[i]; int j = i; for (; j > 0 && temp < arr[j - 1]; j--) { // 如果缓存起来的数小于和它比较的数a，数a移动到下一个位置 arr[j] = arr[j - 1]; } // 两种情况需要把缓存起来的数复制回原数组 // 1、缓存起来的数大于和它比较的数 // 2、和它比较的数的下标为0的时候，因为下标为0的数已经和它比较过并且此时已经被复制到了下标为1处，下标为0的位置就是专门留给它的 arr[j] = temp; } } static void fill(int[] arr) { Random random = new Random(); for (int i = 0; i < 100; i++) { int num = random.nextInt(100); arr[i] = num; } } static void print(int[] arr) { for (int i = 0; i < 100; i++) { System.out.print(arr[i] + " | "); } } }
表插入排序
利用有序链表可以实现一种高效的排序。
算法：假设有一个无序数组，从这个数组中取出数据，一个个插入有序链表；所有数据都插入有序链表后，再从链表中一个个删除，重新放入数组。
效率：
时间复杂度，这种排序比插入排序更快一些。插入排序平均比较N2/4，平均复制N2/4；表插入排序，平均比较N2/4，每个数据项只进行两次复制，一次从数组到链表，一次从链表到数组，所以复制次数是2*N。
空间复杂度，表插入排序的空间复杂度是插入排序的两倍。