基本思想假设待排序的记录存放在数组R[0..n-1]中。初始时，R[0]自成1个有序区，无序区为R[1..n-1]。从i=1起直至i=n-1为止，依次将R[i]插入当前的有序区R[0..i-1]中，生成含n个记录的有序区。算法实现直接插入排序算法，Java实现，代码如下所示： 01 public abstract class Sorter { 02 public abstract void sort(int[] array); 03 } 04 05 public class StraightInsertionSorter extends Sorter { 06 07 @Override 08 public void sort(int[] array) { 09 int tmp; 10 for (int i = 1; i < array.length; i++) { 11 tmp = array[i]; // array[i]的拷贝 12 // 如果右侧无序区第一个元素array[i] < 左侧有序区最大的array[i-1]， 13 // 需要将有序区比array[i]大的元素向后移动。 14 if (array[i] < array[i - 1]) { 15 int j = i - 1; 16 while (j >= 0 && tmp < array[j]) { // 从右到左扫描有序区 17 array[j + 1] = array[j]; // 将左侧有序区中元素比array[i]大的array[j+1]后移 18 j--; 19 } 20 // 如果array[i]>=左侧有序区最大的array[i-1]，或者经过扫描移动后，找到一个比array[i]小的元素 21 // 将右侧无序区第一个元素tmp = array[i]放到正确的位置上 22 array[j + 1] = tmp; 23 } 24 } 25 } 26 } 直接插入排序算法，Python实现，代码如下所示： 01 class Sorter: 02 ''' 03 Abstract sorter class, which provides shared methods being used by 04 subclasses. 05 ''' 06 __metaclass__ = ABCMeta 07 08 @abstractmethod 09 def sort(self, array): 10 pass 11 12 class StraightInsertionSorter(Sorter): 13 ''' 14 Straight insertion sorter 15 ''' 16 def sort(self, array): 17 i = 0 18 length = len(array) 19 while i<length -1: 20 k = i 21 j = i 22 while j<length: 23 if array[j]<array[k]: 24 k = j 25 j = j + 1 26 if k!=i: 27 array[k], array[i] = array[i], array[k] 28 i = i + 1 排序过程直接插入排序的执行过程，如下所示：初始化无序区和有序区：数组第一个元素为有序区，其余的元素作为无序区。遍历无序区，将无序区的每一个元素插入到有序区正确的位置上。具体执行过程为：每次取出无序区的第一个元素，如果该元素tmp大于有序区最后一个元素，不做任何操作；如果tmp小于有序区最后一个元素，说明需要插入到有序区最后一个元素前面的某个位置，从后往前扫描有序区，如果有序区元素大于tmp，将有序区元素后移（第一次后移：tmp小于有序区最大的元素，有序区最大的元素后移覆盖无序区第一个元素，而无序区第一个元素的已经拷贝到tmp中；第二次后移：tmp小于有序区从后向前第二个的元素，有序区从后向前第二个元素后移覆盖有序区最大元素的位置，而有序区最后一个元素已经拷贝到无序区第一个元素的位置上；以此类推），直到找到一个元素比tmp小的元素（如果没有找到，就插入到有序区首位置），有序区后移操作停止。接着，将tmp插入到：从有序区由前至后找到的第一个比tmp小的元素的后面即可。此时，有序区增加一个元素，无序区减少一个元素，直到无序区元素个数为0，排序结束。下面，通过实例来演示执行直接插入排序的过程，假设待排序数组为array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，数组大小为20，则执行排序过程如下所示：初始有序区为{94}，无序区为{12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}。对于array[1] = 12（无序区第一个元素）：临时拷贝tmp = array[1] = 12，tmp = 12小于有序区{94}最后一个元素(94)，因为有序区只有一个元素，所以将tmp插入到有序区首位置，此时，有序区为{12,94}，无序区为{34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}。对于array[2] = 34（无序区第一个元素）：临时拷贝tmp = array[2] = 34，tmp = 34小于有序区{12,94}最后一个元素(94)，将94后移覆盖array[2]，亦即：array[2] = 94；继续将tmp = 34与有序区{12,94}从后向前第二个元素比较，tmp = 34 > 12，则直接将tmp = 34插入到12后面的位置。此时，有序区为{12,34,94}，无序区为{76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}。对于array[3] = 76（无序区第一个元素）：临时拷贝tmp = array[3] = 76，tmp = 76小于有序区{12,34,94}最后一个元素(94)，将94后移覆盖array[3]，亦即：array[3] = 94；继续将tmp = 76与有序区{12,34,94}从后向前第二个元素比较，tmp = 76 > 34，则直接将tmp = 76插入到34后面的位置。此时，有序区为{12,34,76,94}，无序区为{26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}。 …… 依此类推执行，直到无序区没有元素为止，则有序区即为排序后的数组。算法分析时间复杂度最好情况：有序通过直接插入排序的执行过程可以看到，如果待排序数组恰好为有序，则每次从大小为n-1的无序区数组取出一个元素，和有序区最后一个元素比较，一定是比最后一个元素大，需要插入到有序区最后一个元素的后面，也就是原地插入。可见，比较次数为n-1次，数组元素移动次数为0次。最坏情况：逆序每次从无序区取出第一个元素，首先需要与有序区最后一个元素比较一次，然后继续从有序区的最后一个元素比较，直到比较到有序区第一个元素，然后插入到有序区首位置。每次从无序区取出第一个元素，移动放到拷贝tmp中，然后再将tmp与有序区元素比较，这个比较过程一共移动的次数为：有序区数组大小，最后还要将拷贝tmp移动插入到有序区的位置上。在这个过程中：有序区数组大小为1时，比较2次，移动3次；有序区数组大小为2时，比较3次，移动4次； …… 有序区数组大小为n-1时，比较n次，移动n+1次。可见：比较的次数为：2+3+……+n = (n+2)(n-1)/2 移动的此时为：3+4+……+n+1 = (n+4)(n-1)/2 通过上面两种情况的分析，直接插入排序的时间复杂度为O(n2)。空间复杂度在直接插入排序的过程中，只用到一个tmp临时存放待插入元素，因此空间复杂度为O(1)。排序稳定性通过上面的例子来看：当有序区为{0,9,12,26,34,37,55,76,94}，无序区为{76,37,5,68,83,90,37,12,65,76,49}的时候，执行下一趟直接插入排序：对于array[9] = 76（无序区第一个元素）：临时拷贝tmp = array[9] = 76，tmp = 76小于有序区{0,9,12,26,34,37,55,76,94}最后一个元素(94)，将94后移覆盖array[9]，亦即：array[9] = 94；继续将tmp = 76与有序区{0,9,12,26,34,37,55,76,94}从后向前第二个元素(76)比较，tmp = 76 = 76，则直接将tmp = 76插入到有序区数组元素76后面的位置。此时，有序区为{0,9,12,26,34,37,55,76,76,94}，无序区为{37,5,68,83,90,37,12,65,76,49}。继续执行直至完成的过程中，对于两个相等的数组元素，原始为排序数组中索引位置的大小关系并没有发生改变，也就是说，对于值相等的元素e，存在ei1，ei2，……eik，其中i1，i2……ik是数组元素e在为排序数组中的索引位置，排序前有i1<i2<……<ik，排序后仍然有j1<j2<……<jk，其中j1<j2<……<jk为排序后值相等的元素e的索引。可见，直接插入排序是稳定的。

发表了文章 2016-04-13

内部排序算法：直接选择排序

基本思想 n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：初始状态：无序区为R[1..n]，有序区为空。第1趟排序：在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1] 交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 …… 第i趟排序：第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R[i..n](1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[i]交换，使R[1..i] 和R[i+1..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。算法实现直接选择排序算法，Java实现，代码如下所示： 01 public abstract class Sorter { 02 public abstract void sort(int[] array); 03 } 04 05 public class StraightSelectionSorter extends Sorter { 06 07 @Override 08 public void sort(int[] array) { 09 int tmp; // 用于交换数据的暂存单元 10 for (int i = 0; i < array.length - 1; i++) { // 这里只要从0~array.length-2即可 11 int k = i; 12 for (int j = i + 1; j < array.length; j++) { // 该循环可以找到右侧无序区最小的元素array[k] 13 if (array[k] > array[j]) { 14 k = j; 15 } 16 } 17 if (k != i) { // 如果array[i]不是无序区最小的，需要与无序区最小的进行交换 18 tmp = array[i]; 19 array[i] = array[k]; 20 array[k] = tmp; 21 } 22 // 如果array[i]是无序区最小的元素，不需要执行交换 23 } 24 } 25 } 直接选择排序算法，Python实现，代码如下所示： 01 class Sorter: 02 ''' 03 Abstract sorter class, which provides shared methods being used by 04 subclasses. 05 ''' 06 __metaclass__ = ABCMeta 07 08 @abstractmethod 09 def sort(self, array): 10 pass 11 12 class StraightSelectionSort(Sorter): 13 ''' 14 Straight selection sorter 15 ''' 16 def sort(self, array): 17 i = 0 18 length = len(array) 19 while i<length -1: 20 k = i 21 j = i 22 while j<length: 23 if array[j]<array[k]: 24 k = j 25 j = j + 1 26 if k!=i: 27 array[k], array[i] = array[i], array[k] 28 i = i + 1 排序过程首先，从0~n-1个元素中找到最小的元素，交换到0位置上；其次，再从1~n-1中找到次最小的元素，交换到1位置上； ……；最后从n-2~n-1中找到最小的元素，交换到n-2位置上。n-1位置上一定是最大的元素，所以总共进行n-1趟选择排序。需要注意的是：每次确定无序区后，其中除了第一个元素之外的其它元素（设为e）与第一个元素（设为E）比较，只有满足e<E的时候才需要交换一次。排序过程示例如下：假设待排序数组为array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，数组大小为20。第1趟选择排序从array[1,n-1]中找到最小的元素： array[0] = 94>array[1] = 12，交换array[0]与array[1]，即array[0] = 12array[2] = 34不成立，不交换； array[0] = 12>array[3] = 76不成立，不交换； array[0] = 12>array[4] = 26不成立，不交换； array[0] = 12>array[5] = 9，交换array[0]与array[5]，即array[0] = 9array[6] = 0，交换array[0]与array[6]，即array[0] = 0array[7] = 37不成立，不交换； array[0] = 0>array[8] = 55不成立，不交换； array[0] = 0>array[9] = 76不成立，不交换； array[0] = 0>array[10] = 37不成立，不交换； array[0] = 0>array[11] = 5不成立，不交换； array[0] = 0>array[12] = 68不成立，不交换； array[0] = 0>array[13] = 83不成立，不交换； array[0] = 0>array[14] = 90不成立，不交换； array[0] = 0>array[15] = 37不成立，不交换； array[0] = 0>array[16] = 12不成立，不交换； array[0] = 0>array[17] = 65不成立，不交换； array[0] = 0>array[18] = 76不成立，不交换； array[0] = 0>array[19] = 49不成立，不交换。此时数组状态如下：{0,94,34,76,26,12,9,37,55,76,37,5,68,83,90,37,12,65,76,49}。此时，有序区为{0}，无序区为{94,34,76,26,12,9,37,55,76,37,5,68,83,90,37,12,65,76,49}。第2趟选择排序从array[2,n-1]中找到最小的元素： array[1] = 94>array[2] = 34，交换array[1]与array[2]，即array[1] = 34array[3] = 76不成立，不交换； array[1] = 34>array[4] = 26，交换array[1]与array[4]，即array[1] = 26array[5] = 12，交换array[1]与array[5]，即array[1] = 12array[6] = 9，交换array[1]与array[6]，即array[1] = 9array[7] = 37不成立，不交换； array[1] = 0>array[8] = 55不成立，不交换； array[1] = 0>array[9] = 76不成立，不交换； array[1] = 0>array[10] = 37不成立，不交换； array[1] = 9>array[11] = 5，交换array[1]与array[11]，即array[1] = 5array[12] = 68不成立，不交换； array[1] = 5>array[13] = 83不成立，不交换； array[1] = 5>array[14] = 90不成立，不交换； array[1] = 5>array[15] = 37不成立，不交换； array[1] = 5>array[16] = 12不成立，不交换； array[1] = 5>array[17] = 65不成立，不交换； array[1] = 5>array[18] = 76不成立，不交换； array[1] = 5>array[19] = 49不成立，不交换。此时数组状态如下：{0,5,94,76,34,26,12,37,55,76,37,9,68,83,90,37,12,65,76,49}。此时，有序区为{0,5}，无序区为{94,76,34,26,12,37,55,76,37,9,68,83,90,37,12,65,76,49}。第3趟选择排序排序后数组状态为：{0,5,9,94,76,34,26,37,55,76,37,12,68,83,90,37,12,65,76,49}。此时，有序区为{0,5,9}，无序区为{94,76,34,26,37,55,76,37,12,68,83,90,37,12,65,76,49}。第4趟选择排序排序后数组状态变化： {0,5,9,76,94,34,26,37,55,76,37,12,68,83,90,37,12,65,76,49}， {0,5,9,34,94,76,26,37,55,76,37,12,68,83,90,37,12,65,76,49}， {0,5,9,26,94,76,34,37,55,76,37,12,68,83,90,37,12,65,76,49}， {0,5,9,12,94,76,34,37,55,76,37,26,68,83,90,37,12,65,76,49}， {0,5,9,12,94,76,34,37,55,76,37,26,68,83,90,37,12,65,76,49}，此时，有序区为{0,5,9,12}，无序区为{94,76,34,37,55,76,37,26,68,83,90,37,12,65,76,49}。 …… 第n-1趟选择排序依此类推，执行n-1趟选择排序，最后得到：有序区为{0,5,9,12,12,26,34,37,37,37,49,55,65,68,76,76,76,83,90}，无序区为{94}，此时整个数组已经有序，n-1趟选择排序后，排序完成。算法分析时间复杂度记录比较次数：无论待排序数组初始状态如何，都要进行n-1趟选择排序：第1趟：比较n-1次；第2趟：比较n-2次； …… 第n-1趟：比较1次。从而，总共的比较次数为：1+2+……+(n-1) = n(n-1)/2 记录移动次数：如果待排序数组为正序，则记录不需要交换，记录移动次数为0；如果当排序数组为逆序，则：第1趟：交换1次，移动3次；第2趟：交换1次，移动3次； …… 第n-1趟：交换1次，移动3次。从而，总共的移动次数为：3(n-1) = 3(n-1)。因此，时间复杂度为O(n2)。空间复杂度在选择排序的过程中，设置一个变量用来交换元素，所以空间复杂度为O(1)。排序稳定性选择排序是就地排序。通过上面的排序过程中数组的状态变化可以看出：直接选择排序是不稳定的。

发表了文章 2016-04-13

内部排序算法：冒泡排序

基本思想将被排序的记录数组R[0..n-1]垂直排列，每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R：凡扫描到违反本原则的轻气泡，就使其向上”飘浮”。如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。具体过程，如下所示：初始状态：R[0..n-1]为无序区。第一趟扫描：从无序区底部向上依次比较相邻的两个气泡的重量，若发现轻者在下、重者在上，则交换二者的位置，即依次比较(R[n-1], R[n-2])、(R[n-2], R[n-3])、…、(R[1], R[0])；对于每对气泡(R[j+1], R[j])，若R[j+1].key第一趟扫描完毕时，”最轻”的气泡就飘浮到该区间的顶部，即关键字最小的记录被放在最高位置R[0]上。第二趟扫描：扫描R[1..n-1]。扫描完毕时，”次轻”的气泡飘浮到R[1]的位置上……最后，经过n-1趟扫描可得到有序区R[0..n-1]。注意：第i趟扫描时，R[0..i-1]和R[i..n-1]分别为当前的有序区和无序区。扫描仍是从无序区底部向上直至该区顶部。扫描完毕时，该区中最轻气泡飘浮到顶部位置R[i]上，结果是R[0..i]变为新的有序区。算法实现冒泡排序算法，Java实现，代码如下所示： 01 public abstract class Sorter { 02 public abstract void sort(int[] array); 03 } 04 05 public class BubbleSorter extends Sorter { 06 07 @Override 08 public void sort(int[] array) { 09 int tmp; // 用于交换数据的暂存单元 10 for (int i = array.length - 1; i >= 0; i--) { // 将数组最小索引一端视为“水面” 11 // 将数组最小索引一端视为“水底”，“气泡”从“水底”向“水面”上浮 12 // 因为i每增加1，就有一个上浮到最终排序位置，所以，只需要对1~i个元素进行交换排序 13 for (int j = 1; j <= i; j++) { 14 if (array[j - 1] < array[j]) { // 如果上浮过程中发现存在比当前元素小的，就交换，将小的交换到“水面” 15 tmp = array[j - 1]; 16 array[j - 1] = array[j]; 17 array[j] = tmp; 18 } 19 } 20 } 21 } 22 } 冒泡排序算法，Python实现，代码如下所示： 01 class Sorter: 02 ''' 03 Abstract sorter class, which provides shared methods being used by 04 subclasses. 05 ''' 06 __metaclass__ = ABCMeta 07 08 @abstractmethod 09 def sort(self, array): 10 pass 11 12 class BubbleSorter(Sorter): 13 ''' 14 Bubble sorter 15 ''' 16 def sort(self, array): 17 length = len(array) 18 i = length - 1 19 while i>=0: 20 j = 1 21 while j<=i: 22 if array[j-1]<array[j]: 23 array[j-1], array[j] = array[j], array[j-1] 24 j = j + 1 25 i = i - 1 排序过程冒泡排序的执行过程如下：首先，将待排序数组视为一个无序区。从数组一端开始，让元素小的逐步移动到另一端，称为气泡的上浮过程，直到整个数组变成一个有序区。下面，我们通过例子还说明排序过程。假设待排序数组为array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，数组大小为20。将数组最小索引一端视为“水底”，排序过程如下所示： 01 {94,34,76,26,12,9,37,55,76,37,5,68,83,90,37,12,65,76,49, 0} 02 {94,76,34,26,12,37,55,76,37,9,68,83,90,37,12,65,76,49, 5,0} 03 {94,76,34,26,37,55,76,37,12,68,83,90,37,12,65,76,49, 9,5,0} 04 {94,76,34,37,55,76,37,26,68,83,90,37,12,65,76,49, 12,9,5,0} 05 {94,76,37,55,76,37,34,68,83,90,37,26,65,76,49, 12,12,9,5,0} 06 {94,76,55,76,37,37,68,83,90,37,34,65,76,49, 26,12,12,9,5,0} 07 {94,76,76,55,37,68,83,90,37,37,65,76,49, 34,26,12,12,9,5,0} 08 {94,76,76,55,68,83,90,37,37,65,76,49, 37,34,26,12,12,9,5,0} 09 {94,76,76,68,83,90,55,37,65,76,49, 37,37,34,26,12,12,9,5,0} 10 {94,76,76,83,90,68,55,65,76,49, 37,37,37,34,26,12,12,9,5,0} 11 {94,76,83,90,76,68,65,76,55, 49,37,37,37,34,26,12,12,9,5,0} 12 {94,83,90,76,76,68,76,65, 55,49,37,37,37,34,26,12,12,9,5,0} 13 {94,90,83,76,76,76,68, 65,55,49,37,37,37,34,26,12,12,9,5,0} 14 {94,90,83,76,76,76, 68,65,55,49,37,37,37,34,26,12,12,9,5,0} 15 {94,90,83,76,76, 76,68,65,55,49,37,37,37,34,26,12,12,9,5,0} 16 {94,90,83,76, 76,76,68,65,55,49,37,37,37,34,26,12,12,9,5,0} 17 {94,90,83, 76,76,76,68,65,55,49,37,37,37,34,26,12,12,9,5,0} 18 {94,90, 83,76,76,76,68,65,55,49,37,37,37,34,26,12,12,9,5,0} 19 {94, 90,83,76,76,76,68,65,55,49,37,37,37,34,26,12,12,9,5,0} 20 { 94,90,83,76,76,76,68,65,55,49,37,37,37,34,26,12,12,9,5,0} 上图是冒泡排序过程中执行各趟排序，整个数组中元素的位置信息：左上半部分是无序区，右下半部分是有序区。算法分析时间复杂度最好情况：有序数组元素需要两两比较，一趟排序完成。比较次数：n-1 交换次数：0 最坏情况：逆序需要进行n-1趟排序。有序区数组大小为0时：比较n-1次，交换n-1次，移动3(n-1)次；有序区数组大小为1时：比较n-2次，交换n-2次，移动3(n-2)次； …… 有序区数组大小为n-3时：比较2次，交换2次，移动3*2次；有序区数组大小为n-2时：比较1次，交换1次，移动3*1次；比较次数为：1+2+……+(n-1) = n(n-1)/2 移动次数为：3(1+2+……+(n-1)) = 3n(n-1)/2 综上，冒泡排序的时间复杂度为O(n2)。空间复杂度冒泡排序属于交换排序，在排序过程中，只需要用到一个用来执行元素交换的变量即可。因此，空间复杂度为O(1)。排序稳定性冒泡排序是就地排序。冒泡排序是稳定的。

shiyanjuncn_个人页

个人介绍

擅长的技术

HBase-0.90.4集群安装配置

Maven构建应用程序常用配置

Apache Mina通信框架架构与应用

MIna框架I/O Service层设计

MIna框架I/O Filter Chain层设计

使用libsvm进行分类预测

Hadoop MapReduce编程：计算最大值

CentOS 6.4单机环境下安装配置Storm

Mina框架IoService通用抽象服务详解

Hadoop MapReduce处理海量小文件：自定义InputFormat和RecordReader

Mina框架IoHandler与IoProcessor详解

Mina框架IoSession详解

Dubbo架构设计详解

Hadoop Streaming原理及实践

Dubbo实现RPC调用使用入门

基于Dubbo的Hessian协议实现远程调用

CentOS 6.4上HAProxy-1.4.24安装配置

Hadoop Job使用第三方依赖jar文件

开发JAX-WS 2.0 Web服务

JVM 分代GC策略分析

分类算法：决策树（ID3）

Solr DIH: 基于MySQL表数据建立索引

分类算法：决策树（C4.5）

基于Solr DIH实现MySQL表数据全量索引和增量索引

ZooKeeper-3.3.4集群安装配置

ZooKeeper应用案例

Impala与HBase整合实践

k-means聚类算法原理及其实现

DBSCAN聚类算法原理及其实现

MapReduce V1：JobTracker端Job/Task数据结构

MapReduce V1：Job提交流程之JobTracker端分析

MapReduce V1：Job提交流程之JobClient端分析

Akka框架基本要点介绍

JStorm-0.9.6.2安装配置

Hue安装配置实践

HDFS写文件过程分析

Flume(NG)架构设计要点及配置实践

HDFS读文件过程分析：获取文件对应的Block列表

Shark-0.9.0安装配置运行实践

RDD：基于内存的集群计算容错抽象

Oozie Coordinator使用及详解

Oozie-3.3.2安装配置运行实践

使用libsvm实现文本分类

CentOS 6.4系统MySQL主从复制基本配置实践

使用Sqoop job工具同步数据

Sqoop-1.4.4工具import和export使用详解

CentOS 6.4下安装配置Spark-0.9集群

内部排序算法：直接插入排序