排序算法原理与代码实现

1、直接插入排序与希尔排序

• 直接插入排序

直接插入排序算法步骤分为两步：
首先，将第一个元素当成一个有序的序列，然后将第二个元素到最后一个元素当成是一个未排序的序列。
其次，扫描未排序的序列，将扫描到的每个元素插入到有序序列的适当位置。也就是说它会和有序序列的元素从末尾到头部依次比较，并找到自己的位置。

Java实现：

public static void insertSort(int[] array) {
  int size = array.length;
  for(int i=1; i<size; i++) { //i从1开始表明我们假设a[0]已经放好了位置
      int temp = array[i];
      int j;
      //比较当前元素和该元素之前所有元素的大小，将比该元素大的后移
      for(j=i-1; j>=0 && a[j]>temp; j--) { 
          a[j+1] = a[j];
      }
      a[j+1] = temp; //插入到正确的位置
  }
}

总结分析：
当最好的情况，也就是排序的表本身是有序的，那么我们比较的次数就是n-1次，没有移动记录，此时时间复杂度是O(n)。当最坏的情况，即待排序的表是逆序的情况下，此时的时间复杂度是O(n^2)。 平均情况下，时间复杂度是O(n^2)。
从空间上来看，它只需要一个辅助的空间来进行临时数据的存储，空间复杂度是O(1)。
直接插入排序的稳定性分析：由于直接插入排序比较的是相邻的元素，而且也不存在跳跃性比较和交换，所以它是一种稳定的排序方法。

• 希尔排序

希尔排序是对直接插入排序的改进。我们可以将待排序序列分割为若干个子序列，此时子序列待排序的记录个数就比较少了，然后在这些子序列内分别进行直接插入排序，当整个序列基本有序时，注意只是基本有序时，再对全体记录进行一次直接插入排序。所谓的基本有序，就是小的关键字基本在前面，大的基本在后面，不大不小的基本在中间。

对于上面的解释中的若干个子序列的定义我们需要转换一下思想：
我们将相距某个“增量”的记录组成一个子序列。如下表所示，当增量为4时，9和3，1和7，5和4，8和6，2组成子序列，在子序列中将小的排在前面，大的排在后面。排完一轮后，增量变化为2时，然后下标0和2，下标1和3，...组成子序列，又排完一轮后，增量变化为1，这个时候希尔排序变成了直接插入排序，这个时候序列经过前面几轮的排序已经变得基本有序了，所以使用直接插入排序变得很高效。

下标	0	1	2	3	4	5	6	7	8
***	9	1	5	8	3	7	4	6	2

Java实现：(将直接插入排序的1使用increment代替，因为当increment为1时就是直接插入排序)

public static void shellSort(int[] array) {
  int size = array.length;
  int increment = size;
  while(increment > 1) {
      increment = increment / 3 + 1; //增量序列的一种获取算法，也可以用其他的算法
      for(int i=increment; i<size; i++) {
        int temp = array[i];
        int j;
        for(j=i-increment; j>=0 && a[j]>temp; j-=increment) { 
          a[j+increment] = a[j];
        }
        a[j+increment] = temp; 
      }
  }
}

总结分析：
大量的数据表明，在最好的情况下，希尔排序的时间复杂度是O(n^1.3)。 最坏的情况是O(n^2)。 平均情况是O(nlog2n)~O(n^2)。
空间复杂度也是O(1)。
稳定性方面由于是跳跃性的移动，所以希尔排序是一种不稳定的排序方法。

2、冒泡排序与快速排序

• 冒泡排序

冒泡排序是一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

Java实现：

public static void bubbleSort(int[] array) {
        boolean swapped = true; //swapped作为标记
        int length = array.length;
        for (int i = 0; swapped && i < length - 1; i++) { //若swapped为false则退出循环，注意i的值是小于length-1的
            swapped = false; //初始化为false
            for (int j = length - 1; j > i; j--) { //从后往前循环
                if (array[j] < array[j - 1]) {
                    int temp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                    swapped = true; //如果数据有效，swapped为true
                }
            }
        }
    }

总结分析
最好的情况下，也就是排序的表本身是有序的，那么我们只是比较而没有数据交换，可以判断出就是n-1次比较，没有数据交换，时间复杂度为O(n)。当最坏的情况下，即待排序的表是逆序的情况下，此时需要比较n-1+n-2+......+2+1=n(n-1)/2次，并作等数量级的记录移动，因此，总的时间复杂度是O(n^2)。
整个排序过程中只用到了一个临时变量来存储待要交换的数据，故空间复杂度为O(1)。
冒泡排序是因为是相邻的元素两两比较和交换，故冒泡排序是一种稳定的排序方法。

• 快速排序

快速排序的基本思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分继续进行排序，以达到整个序列有序的目的。

Java实现：

public static void quickSort(int[] array) {
  int low = 0, high = array.length - 1;
  int pivot; //枢纽，中心点
  while(low < high) {
    pivot = partition(array, low, high); //将array分为low到pivot - 1，pivot+1到high两部分
    quickSort(array, low, pivot -1); //对低字表递归排序
    low = pivot + 1; //尾递归
  }
}

public static int partition(int[] array, int low, int high) {
  int m = (low + high) / 2; //数组中间元素的下标
  if(array[low] > array[high]) {
    swap(array, low, high); //交换左端与右端的元素，保证左端较小
  }
  if(array[m] > array[high]) {
    swap(array, m, high); //交换中间和右端的元素，保证中间较小
  }
  if(array[m] > a[low]) {
    swap(array, m, low); //交换中间与左端数据，保证左端较大
  }
  //此时array[low]已经是整个序列左中右三个关键字的中间值
  int pivot = a[low];
  while(low < high) {
    while(low < high && array[high] >= pivot) {
      high--;
    }
    swap(array, low, high);
    while(low < high && array[low] <= pivot) {
      low++;
    }
    swap(array, low, high);
  }
  return low; //此时low=high，返回其之一就行
}

总结分析：
快速排序的调用，时间性能取决于快速排序递归的深度。在最优的情况下，partition每次都划分得很均匀，此时时间复杂度为O(nlogn)。在最坏的情况下，待排序序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，注意另一个为空。如果递归树画出来，它是一颗斜树，此时的时间复杂度为O(n^2)。 平均情况下，时间复杂度为O(nlogn)。
空间复杂度主要是递归造成的栈的使用，最好情况下，递归树的深度为logn，其空间复杂度为O(logn)。最坏情况下，需要进行n-1次递归调用，其空间复杂度为O(n)。平均情况下，空间复杂度也为O(logn)。
由于快速排序关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。

3、简单选择排序与堆排序

• 简单选择排序

简单选择排序的基本思想是：通过n-i次关键字间的比较，从n-i+1个记录中选出关键字最小的记录，并和第i（1<=i<=n）个记录交换。

Java实现

public static void simpleSelectSort(int[] array) {
        int length = array.length;
        int min;
        for (int i = 0; i < length; i++) {
            min = i;
            for (int j = i+1; j < length; j++) {
                if (array[j] < array[min]) {
                    min = j;
                }
            }
            if (min != i) {
                int temp = array[min];
                array[min] = array[i];
                array[i] = temp;
            }
        }
    }

• 堆排序

堆排序是对简单选择排序的一种改进。堆是具有下列性质的完全二叉树：每个节点的值都大于或者等于其左右孩子节点的值，称为大顶堆；或者每个节点的值都小于等于其左右孩子节点的值，称为小顶堆。
堆排序的基本思想是：将待排序的序列构造成一个大顶推。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是讲起与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩下的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值。如此反复执行，便得到一个有序的序列。

Java实现：

public static void heapSort(int[] array, int n) {
         //这里的数组从第一位开始才有值，主要是为了对应完全二叉树的性质。n表示有值的元素的长度
        for(int i = n / 2; i > 0;i--) {
            heapAdjust(array, i, n);
        }
        for (int i = n; i > 1; i--) {
            swap(array, 1, i); //交换数组两个下标的数
            heapAdjust(array, 1, i - 1);
        }
    }

    public static void heapAdjust(int[] a, int s, int m) {
        int i;
        int temp = a[s]; //将第一个非终端结点保存
        for (i = 2 * s; i <= m; i*=2) {
            if (i < m && a[i] < a[i + 1]) { //i<m表明存在左、右孩子
                i++; //右孩子比较大，则i+1，否则i不变
            }
            if (temp >= a[i]) { //比较结点和较大的记录，若结点较大，则退出for循环，不用交换数据
                break;
            }
            //否则将a[i]插入到结点的位置
            a[s] = a[i];
            s = i; //由于有数据交换，破坏了以位置s为根节点的堆的性质，于是将i赋值给s
        }
        a[s] = temp; //最后将temp插入到a[s]的位置
    }