排序算法笔记二

排序六：直接选择排序

直接选择排序也是一种简单的排序方法，它的基本思想是：第一次从data[0]~data[n-1]中选取最小值，与data[0]交换，第二次从data[1]~data[n-1]中选取最小值，与data[1]交换，....，第i次从data[i-1]~data[n-1]中选取最小值，与data[i-1]交换，.....，第n-1次从data[n-2]~data[n-1]中选取最小值，与data[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。

int[] data= { 31, 23, 89, 10, 47, 68, 8, 22 };

【31 23 89 10 47 68 8 22 】data[0]=31与最小data[6]=8交换
【8 23 89 10 47 68 31 22 】data[1]=23与后面最小值data[3]=10交换
【8 10 89 23 47 68 31 22 】data[2]=89与后面最小值data[7]=22交换
【8 10 22 23 47 68 31 89 】data[3]=23小于后面的值，不用交换
【8 10 22 23 47 68 31 89 】data[4]=47与后面最小值data[6]=31交换
【8 10 22 23 31 68 47 89 】data[5]=68与后面最小值data[6]=47交换
【8 10 22 23 31 47 68 89 】data[6]=68小于后面的值，不用交换
排序完成

从小到大排序：

public class Sort {
    public static void main(String[] args) {
        int[] data = { 31, 23, 89, 10, 47, 68, 8, 22 };
        selectSort(data);
        showData(data);
    }

    // 打印数组
    private static void showData(int[] data) {
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i] + " ");
        }
    }
    
    // 直接选择排序
        private static void selectSort(int[] data) {
            int n = data.length;
            int i, j, k;
            int t;
            for (i = 0; i < n - 1; i++) {// 做第i趟排序(1≤i≤n-1)
                k = i;
                for (j = i + 1; j < n; j++) {
                    // 在当前无序区data[i..n]中选key最小的记录data[k]
                    if (data[j] < data[k]) {
                        k = j; // k记下目前找到的最小关键字所在的位置
                    }
                }
                if (k != i) { // 交换data[i]和data[k]
                    t = data[i];
                    data[i] = data[k];
                    data[k] = t; // t作暂存单元
                }
            }
        }
}

排序七：堆排序

1.堆排序是指利用堆这种数据结构所设计的一种选择排序。

堆实际上是一棵完全二叉树，其任何一非叶节点满足性质：Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]。

堆分为大顶堆和小顶堆，满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆，满足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。

2.用大根堆排序的基本思想：

（1）用大根堆排序的基本思想

① 先将初始文件R[1..n]建成一个大根堆，此堆为初始的无序区

② 再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key

③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。

……

直到无序区只有一个元素为止。

（2）大根堆排序算法的基本操作：

① 初始化操作：将R[1..n]构造为初始堆；

② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。

因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。

 

下面举例对31, 23, 89, 10, 47, 68, 8, 22进行堆排序。

首先根据该数组元素构建一个完全二叉树：

 

 

然后需要构造初始堆，则从最后一个非叶节点开始调整，调整过程如下：

10小于22，交换后

接着看上一个节点，89都比他的子节点大，不用交换

接着看上一个节点，23节点比它的子节点47小，交换后

接着看上一个节点，31都比它的子节点小，跟左右最大的节点交换，交换后31到89位置，又与它的子节点68小，再次交换，交换后

这样就得到了初始堆。

即每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整)。有了初始堆之后就可以进行排序了。

堆顶89与最后一个节点10交换，交换后10在堆顶位置，与它左右孩子节点小，与最大的右孩子节点68交换，交换后10到68位置又与它的左孩子节点31小，与31交换

交换后数组长度-1，接着堆顶68与最后一个数据即最后第二个节点8交换，8到堆顶位置与左右孩子节点小，8与最大的左孩子节点47交换，交换后8到47位置又与左右孩子节点小，与最大的右孩子节点23交换

交换后数组长度-1，接着堆顶47与最后一个数据即最后第三个节点10交换，10到堆顶与它左右孩子节点小，10与它最大的右孩子节点31交换

交换后数组长度-1，接着堆顶31与最后一个数据即最后第四个节点8交换，8到堆顶位置与它的左右孩子节点小，8与它最大的左孩子节点23交换，交换后8到23位置，又与它的左节点22小（此时右节点不在范围内），8与22交换

交换后数组长度-1，接着堆顶23与最后一个数据即最后第五节点8交换，8到堆顶位置与左右孩子节点小，8与它最大的左孩子节点22交换

交换后数组长度-1，接着堆顶22与最后一个数据即最后第六个节点10交换

交换后数组长度-1，最后堆顶10与最后一个数据即最后第七个节点8交换

这样堆排序就完后了。

代码如下：

public class Sort {
    public static void main(String[] args) {
        int[] data = { 31, 23, 89, 10, 47, 68, 8, 22 };
        heapSort(data);
        showData(data);
    }

    // 打印数组
    private static void showData(int[] data) {
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i] + " ");
        }
    }

    // 堆排序 筛选算法
        private static void sift(int[] data, int i, int n) {
            int j, temp;

            temp = data[i];
            j = 2 * i + 1;
            while (j < n) {
                if (j + 1 < n && data[j + 1] > data[j]) // 在左右孩子中找最大的
                    j++;

                if (data[j] <= temp)
                    break;

                data[i] = data[j]; // 把较大的子结点往上移动,替换它的父结点
                i = j;
                j = 2 * i + 1;
            }
            data[i] = temp;// 堆顶记录填入适当位置
        }

        // 创建大项堆算法
        private static void buildHeap(int[] data, int n) {
            int i;
            for (i = n / 2 - 1; i >= 0; i--) {// 建立初始堆
                sift(data, i, n);
            }
        }

        // 堆排序
        private static void heapSort(int[] data) {
            int n = data.length;
            int i;
            int t;
            buildHeap(data, n);
            for (i = n - 1; i >= 1; i--) {
                t = data[i];// 将堆顶记录与最后一个记录交换
                data[i] = data[0];
                data[0] = t;
                sift(data, 0, i);// 调整堆
            }
        }
}

排序八：归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。

归并操作的基本思想：

1.申请一个临时数组，使其大小为要排序的数组一样大，排序时用来临时存放数据。

2.将要排序的数据以中点分成两组数据各自排序，各自排序也是以各自的中点分成两组数据直到递归分割数据到基本单位；

3.从两个已经排序序列的起始位置比较，选择相对小的元素放入临时数组里，并比较下一位置的数据，直到超出序列尾。

4.将另一序列剩下的所有元素直接复制到临时数组，最后临时数组数据全部赋值给要排序的数组，这样就排序完成了。

下面以31, 23, 89, 10, 47, 68, 8, 22为例：

分为两个子序列31, 23, 89, 10  和  47, 68, 8, 22

再分别将序列31, 23, 89, 10分为两个子序列31, 23和89, 10，序列47, 68, 8, 22分为两个子序列47, 68和8, 22。

分别对这些子序列排序，排序后对两个大子序列进行排序：

这样归并排序就完成了。

代码

public class Sort {
    public static void main(String[] args) {
        int[] data = { 31, 23, 89, 10, 47, 68, 8, 22 };
        mergeSort(data);
        showData(data);
    }

    // 打印数组
    private static void showData(int[] data) {
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i] + " ");
        }
    }
        // 归并排序
        public static void mergeSort(int[] list) {
            int length = list.length;
            int[] temp = new int[length];// 临时数组
            recMergeSort(list, temp, 0, length - 1);
        }

        // 递归分割数据到基本单位
        private static void recMergeSort(int[] list, int[] temp, int low, int upper) {
            if (low == upper) {
                return;
            } else {
                int mid = (low + upper) / 2;
                recMergeSort(list, temp, low, mid);
                recMergeSort(list, temp, mid + 1, upper);
                merge(list, temp, low, mid + 1, upper);
            }
        }

        // 归并操作将基本单位归并成整个有序的数组
        private static void merge(int[] list, int[] temp, int left, int right, int last) {
            int j = 0;
            int lowIndex = left;
            int mid = right - 1;
            int n = last - lowIndex + 1;
            while (left <= mid && right <= last) {
                if (list[left] < list[right]) {
                    temp[j++] = list[left++];
                } else {
                    temp[j++] = list[right++];
                }
            }
            while (left <= mid) {
                temp[j++] = list[left++];
            }
            while (right <= last) {
                temp[j++] = list[right++];
            }
            for (j = 0; j < n; j++) {
                list[lowIndex + j] = temp[j];
            }
        }


}