JAVA版排序算法_int seventh = (length >> 3) (length >> 6) 1;

概述

排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。这里介绍的八个排序算法都属于内排序。

    当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。

   快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；

1.插入排序—直接插入排序(Straight Insertion Sort)

基本思想:

将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。即：先将序列的第1个记录（也可以是多个）看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。

要点：设立哨兵，作为临时存储和判断数组边界之用。

直接插入排序示例：

如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

算法的实现：

效率：

时间复杂度：O（n^2）.最好的情况也就是排序表本身有序，则交换次数为0，比较次数为常数，则为O（n）,但是最坏的情况是排序表本身是逆序的情况，比较和移动一次都为最大，此时时间复杂度为O（n2），若排序表平均，复杂度平均也为O（n2）。

其他的插入排序有二分插入排序，2-路插入排序。

 2. 插入排序—希尔排序（Shell`s Sort）

希尔排序是1959 年由D.L.Shell 提出来的，相对直接排序有较大的改进。希尔排序又叫缩小增量排序

基本思想：

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

操作方法：

1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
2. 按增量序列个数k，对序列进行k 趟排序；
3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

希尔排序的示例：

算法实现：

我们简单处理增量序列：增量序列d = {n/2 ,n/4, n/8 .....1} n为要排序数的个数

即：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。

3. 选择排序—简单选择排序（Simple Selection Sort）

基本思想：

在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

简单选择排序的示例：

操作方法：

第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；

第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；

以此类推.....

第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，

直到整个序列按关键码有序。

算法实现：

 简单选择排序的改进——二元选择排序

简单选择排序，每趟循环只能确定一个元素排序后的定位。我们可以考虑改进为每趟循环确定两个元素（当前趟最大和最小记录）的位置,从而减少排序所需的循环次数。改进后对n个数据进行排序，最多只需进行[n/2]趟循环即可。具体实现如下：

4. 选择排序—堆排序（Heap Sort）

基本思想：

堆的定义如下：具有n个元素的序列（k1,k2,...,kn),当且仅当满足

时称之为堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（小顶堆）。
若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。如：

（a）大顶堆序列：（96, 83,27,38,11,09)

  (b)  小顶堆序列：（12，36，24，85，47，30，53，91）

初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。称这个过程为堆排序。

因此，实现堆排序需解决两个问题：
1. 如何将n 个待排序的数建成堆；
2. 输出堆顶元素后，怎样调整剩余n-1 个元素，使其成为一个新堆。

首先讨论第二个问题：输出堆顶元素后，对剩余n-1元素重新建成堆的调整过程。
调整大顶堆的方法：

1）设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素。将堆底元素送入堆顶（（最后一个元素与堆顶进行交换），堆被破坏，其原因仅是根结点不满足堆的性质。

2）将根结点与左、右子树中较大元素的进行交换。

3）若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法 （2）.

4）若与右子树交换，如果右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法 （2）.

5）继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。

称这个自根结点到叶子结点的调整过程为筛选。如图：

再讨论对n 个元素初始建堆的过程。
建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。

1）n 个结点的完全二叉树，则最后一个结点是第个结点的子树。

2）筛选从第个结点为根的子树开始，该子树成为堆。

3）之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。

如图建堆初始过程：无序序列：（49，38，65，97，76，13，27，49）
                              

import java.util.Arrays;

public class HeapSort {
    
    private int[] arr;
    
    public HeapSort(int[] arr){
        this.arr = arr;
    }
    
    /**
     * 堆排序的主要入口方法，共两步。这里是从小到大递增排序。
     */
    public void sort(){
        /*
         *  第一步：将数组堆化
         *  beginIndex = 第一个非叶子节点。
         *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
         *  叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
         */
        int len = arr.length - 1;
        int beginIndex = (len - 1) >> 1; 
        for(int i = beginIndex; i >= 0; i--){
            maxHeapify(i, len);
        }
        
        /*
         * 第二步：对堆化数据排序
         * 每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，同时遍历长度 - 1。
         * 然后从新整理被换到根节点的末尾元素，使其符合堆的特性。
         * 直至未排序的堆长度为 0。
         */
        for(int i = len; i > 0; i--){
            swap(0, i);
            maxHeapify(0, i - 1);
        }
    }
    
    private void swap(int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    /**
     * 调整索引为 index 处的数据，使其符合堆的特性。
     * 
     * @param index 需要堆化处理的数据的索引
     * @param len 未排序的堆（数组）的长度
     */
    private void maxHeapify(int index,int len){
        int li = (index << 1) + 1; // 左子节点索引
        int ri = li + 1;           // 右子节点索引
        int cMax = li;             // 子节点值最大索引，默认左子节点。
        
        if(li > len) return;       // 左子节点索引超出计算范围，直接返回。
        if(ri <= len && arr[ri] > arr[li]) // 先判断左右子节点，哪个较大。
            cMax = ri;
        if(arr[cMax] > arr[index]){ // 若较大的子节点比父节点大
            swap(cMax, index);      // 如果父节点被子节点调换，
            maxHeapify(cMax, len);  // 则需要继续判断换下后的父节点是否符合堆的特性。
        }
    }
    
    /**
     * 测试用例
     * 
     * 输出：
     * [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9]
     */
    public static void main(String[] args) {
        int[] arr = new int[]{3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6};        
        new HeapSort(arr).sort();        
        System.out.println(Arrays.toString(arr));
    }
    
}

分析:

堆排序主要耗时在建堆和重建堆的反复筛选上。在建初始堆时，对于每个非终节点，最多进行两次比较和互换操作，因此整个初始建堆的时间为O（n）。在进行排序时第i次重建堆需要用O（logi）的时间（完全二叉树的某个结点到根结点的距离为log2i（向下取整）+1)，并且需要取n-1次堆顶记录，因此重建堆的时间复杂度为O（NlogN），堆排序为不稳定排序。

设树深度为k，。从根到叶的筛选，元素比较次数至多2(k-1)次，交换记录至多k 次。所以，在建好堆后，排序过程中的筛选次数不超过下式： 

而建堆时的比较次数不超过4n 次，因此堆排序最坏情况下，时间复杂度也为：O(nlogn )。

细致分析：

    初始化建堆过程时间：O(n)

        推算过程：

        首先要理解怎么计算这个堆化过程所消耗的时间，可以直接画图去理解；

        假设高度为k，则从倒数第二层右边的节点开始，这一层的节点都要执行子节点比较然后交换（如果顺序是对的就不用交换）；倒数第三层呢，则会选择其子节点进行比较和交换，如果没交换就可以不用再执行下去了。如果交换了，那么又要选择一支子树进行比较和交换；

        那么总的时间计算为：s = 2^( i - 1 )  *  ( k - i )；其中 i 表示第几层，2^( i - 1) 表示该层上有多少个元素，( k - i) 表示子树上要比较的次数，如果在最差的条件下，就是比较次数后还要交换；因为这个是常数，所以提出来后可以忽略；

        S = 2^(k-2) * 1 + 2^(k-3)*2.....+2*(k-2)+2^(0)*(k-1)  ===> 因为叶子层不用交换，所以i从 k-1 开始到 1；

        这个等式求解，我想高中已经会了：等式左右乘上2，然后和原来的等式相减，就变成了：

        S = 2^(k - 1) + 2^(k - 2) + 2^(k - 3) ..... + 2 - (k-1)

        除最后一项外，就是一个等比数列了，直接用求和公式：S = {  a1[ 1-  (q^n) ] }  / (1-q)；

        S = 2^k -k +1；又因为k为完全二叉树的深度，所以 2^（k-1） <=  n <= (2^k  -1 )，总之可以认为：k ≈ logn 

        综上所述得到：S = n - longn +1，所以时间复杂度为：O(n)

5. 交换排序—冒泡排序（Bubble Sort）

 public static void bubbleSort(int[] arr) {
    int i, temp, len = arr.length;
    boolean changed;;
    do {
      changed = false;//初始化为没发生数据交换的状态
      for (i = 0; i < len - 1 ; i++) {
        if (arr[i] > arr[i + 1]) {  //前比后大则交换
          temp = arr[i];
          arr[i] = arr[i + 1];
          arr[i + 1] = temp;
          changed = true;//若发生了数据交换，即进入if块
        }
      }
    } while (changed);
  }

private void core(int[] array) {
        int arrayLength = array.length;
 
        int preIndex = 0;
        int backIndex = arrayLength - 1;
        while(preIndex < backIndex) {
            preSort(array, arrayLength, preIndex);
            preIndex++;
 
            if (preIndex >= backIndex) {//若相遇则结束
                break;
            }
 
            backSort(array, backIndex);
            backIndex--;
        }
    }
 
    // 从前向后排序
    private void preSort(int[] array, int length, int preIndex) {
        for (int i = preIndex + 1; i < length; i++) {
            if (array[preIndex] > array[i]) {
                ArrayUtils.swap(array, preIndex, i);
            }
        }
    }
 
    // 从后向前排序
    private void backSort(int[] array, int backIndex) {
        for (int i = backIndex - 1; i >= 0; i--) {
            if (array[i] > array[backIndex]) {
                ArrayUtils.swap(array, i, backIndex);
            }
        }
    }
  
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

1.需要排序的数组为a,判断数组的长度是否大于286，大于使用归并排序（merge sort），否则执行2。 

2.判断数组长度是否小于47，小于则采用直接插入排序，否则执行3。 

3.采用双轴三分快排（两个枢轴：对枢轴的选择是先采用近似算法计算数组长度的1/7，再取中位数做加减来得出包括中位数在内的5个点，最终取第二个和第四个点为枢轴。三个指针：分别是less,k,great。先说一下最终结果，less和great将数组分为3个部分，分别是小于less的，大于less小于great的元素和大于great的元素。 如何达到这个结果呢，初始时，less和great分别指向数组起始的元素和结束的元素。此时，所有的元素在less和great之间，即待处理的元素。随着程序的进行，小于less的元素逐步移动到less左边，大于great的元素移动到great右边。 另外有一个指针k表示处理到哪个元素了，初始值为less，结束值为great（这里的great是会动态改变的，但是大于great的元素一定是处理过的） 

4在排序完成后判断中间的区域是否过大，如果是，则执行5，否则递归执行步骤2。 

5.将等于pivot1或者pivot2的元素移动到两边，然后递归执行步骤2。

int e5 = e4 + seventh;

void MergeSortDC(SeqList R，int low，int high)
 {//用分治法对R[low..high]进行二路归并排序
 int mid；
 if(low<high){//区间长度大于1
  mid=(low+high)/2； //分解
  MergeSortDC(R，low，mid); //递归地对R[low..mid]排序
  MergeSortDC(R，mid+1，high)； //递归地对R[mid+1..high]排序
  Merge(R，low，mid，high)； //组合，将两个有序区归并为一个有序区
 }
 }//MergeSortDC

public class MergeSortTest {
  
 public static void main(String[] args) {
 int[] data = new int[] { 2, 4, 7, 5, 8, 1, 3, 6 };
 System.out.print("初始化：\t");
 print(data);
 System.out.println("");
  
 mergeSort(data, 0, data.length - 1);
   
 System.out.print("\n排序后: \t");
 print(data);
 }
  
 public static void mergeSort(int[] data, int left, int right) {
 if (left >= right)
  return;
 //两路归并
 // 找出中间索引
 int center = (left + right) / 2;
 // 对左边数组进行递归
 mergeSort(data, left, center);
 // 对右边数组进行递归
 mergeSort(data, center + 1, right);
 // 合并
 merge(data, left, center, center + 1, right);
 System.out.print("排序中:\t");
 print(data);
 }
  
 /**
 * 将两个数组进行归并，归并前面2个数组已有序，归并后依然有序
 *
 * @param data
 *  数组对象
 * @param leftStart
 *  左数组的第一个元素的索引
 * @param leftEnd
 *  左数组的最后一个元素的索引
 * @param rightStart
 *  右数组第一个元素的索引
 * @param rightEnd
 *  右数组最后一个元素的索引
 */
 public static void merge(int[] data, int leftStart, int leftEnd,
  int rightStart, int rightEnd) {
 int i = leftStart;
 int j = rightStart;
 int k = 0;
 // 临时数组
 int[] temp = new int[rightEnd - leftStart + 1]; //创建一个临时的数组来存放临时排序的数组
 // 确认分割后的两段数组是否都取到了最后一个元素
 while (i <= leftEnd && j <= rightEnd) {
  // 从两个数组中取出最小的放入临时数组
  if (data[i] > data[j]) {
  temp[k++] = data[j++];
  } else {
  temp[k++] = data[i++];
  }
 }
 // 剩余部分依次放入临时数组（实际上两个while只会执行其中一个）
 while (i <= leftEnd) {
  temp[k++] = data[i++];
 }
 while (j <= rightEnd) {
  temp[k++] = data[j++];
 }
 k = leftStart;
 // 将临时数组中的内容拷贝回原数组中 // （原left-right范围的内容被复制回原数组）
 for (int element : temp) {
  data[k++] = element;
 }
 }
  
 public static void print(int[] data) {
 for (int i = 0; i < data.length; i++) {
  System.out.print(data[i] + "\t");
 }
 System.out.println();
 }
}

public class sort{ 
public static void merge_sort(int[] arr) {
    int len = arr.length;
    int[] result = new int[len];
    int block, start;
    
    
    // 原版代码的迭代次数少了一次，没有考虑到奇数列数组的情况
    for(block = 1; block < len; block *= 2) {//每次划分数组都增大为原来的两倍
        for(start = 0; start <len; start += 2 * block) {//每次都从已经排序好的数组后面开始排序
            int low = start;
            int mid = Math.min(len,strat+bolck);//即不能比len大，bolck为划分后每段的长度,为了碰到奇数列数组时能遍历完
            int high = Math.min(len,strat+2*bolck);
            //两个块的起始下标及结束下标
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            //开始对两个block进行归并排序
            while (start1 < end1 && start2 < end2) {
	        result[low++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
            }
            while(start1 < end1) {
	        result[low++] = arr[start1++];
            }
            while(start2 < end2) {
	        result[low++] = arr[start2++];
            }
        }
     
 
   //arr用作结果记录，每次都把排好序的数组result给arr,使arr保持最新排序状态
   //result用作临时数组
	int[] temp = arr;
	arr = result;
	result = temp;
        
    }
    
    
    //将排序好的结果arr传给result输出
    result = arr;     
}
    //输出结果
    public static void main(String args[]){
        int a[] = {6,6,2,1,3,7,6,2,6};
        System.out.print(a.toString());
        //输出[6, 6, 2, 1, 3, 7, 6, 2, 6]
        merge_sort(a);
        System.out.print(a.toString());
        //输出[1, 2, 2, 3, 6, 6, 6, 6, 7]
    }
}