概述
排序有内部排序和外部排序
- 内部排序是数据记录在内存中进行排序
- 外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存
时间复杂度为最差情况下的复杂度
八大排序就是内部排序
当n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快排,堆排,归排
快速排序：是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短
稳定性:在值相等情况下,相对次序保持不变
#1. 插入排序—直接插入排序(Straight Insertion Sort)
- 基本思想:
将一个记录插入到已排序好的有序表中，从而得到一个新且记录数增1的有序表。即：先将序列的第1个记录看成是一个有序的子序列，然后从第2个记录逐个进行插入，直至整个序列有序为止。 - 要点
设立哨兵，作为临时存储和判断数组边界之用。 - 直接插入排序示例
元素相等的，把欲插入的元素放在相等元素的后面
所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序
所以插入排序稳定
- 实现：
public class InsertionSort { public static void insertionSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 1; i < arr.length; i++) { for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) { swap(arr, j, j + 1); } } } public static void swap(int[] arr, int i, int j) { arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } // for test public static void comparator(int[] arr) { Arrays.sort(arr); } // for test public static int[] generateRandomArray(int maxSize, int maxValue) { int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } // for test public static int[] copyArray(int[] arr) { if (arr == null) { return null; } int[] res = new int[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } // for test public static boolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { return false; } if (arr1 == null && arr2 == null) { return true; } if (arr1.length != arr2.length) { return false; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { return false; } } return true; } // for test public static void printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // for test public static void main(String[] args) { int testTime = 500000; int maxSize = 100; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); insertionSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { succeed = false; break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); insertionSort(arr); printArray(arr); } }
c++版本
void InsertSort(int a[], int n) { for(int i= 1; i<n; i++){ if(a[i] < a[i-1]){ //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入 int j= i-1; int x = a[i]; //复制为哨兵，即存储待排序元素 a[i] = a[i-1]; //先后移一个元素 while(x < a[j]){ //查找在有序表的插入位置 a[j+1] = a[j]; j--; //元素后移 } a[j+1] = x; //插入到正确位置 } print(a,n,i); //打印每趟排序的结果 } }
- 效率：
时间复杂度：O（n^2）
其他的插入排序有二分插入排序，2-路插入排序。
常数项极低,所以样本容量很小时(数组长度小于6)最快!,Collections.sort即是如此设计
2 插入排序—希尔排序（Shell`s Sort）
1959 年由D.L.Shell 提出，相对直接排序有较大的改进
又叫缩小增量排序
- 思想
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序
待整个序列中的记录“基本有序”时
再对全体记录进行依次直接插入排序。
##实现
简单处理增量序列
d = {n/2 ,n/4, n/8 .....1}, n为要排序数的个数
- 先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列
- 每组中记录的
下标相差d,对每组中元素进行直接插入排序 - 再用一个较小的增量（d/2）对它进行分组
- 在每组中再进行
直接插入排序 - 继续不断
缩小增量直至为1，最后使用直接插入排序完成排序
/** * 直接插入排序的一般形式 * * @param int dk 缩小增量，如果是直接插入排序，dk=1 * */ void ShellInsertSort(int a[], int n, int dk) { for(int i= dk; i<n; ++i){ if(a[i] < a[i-dk]){ //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入 int j = i-dk; int x = a[i]; //复制为哨兵，即存储待排序元素 a[i] = a[i-dk]; //首先后移一个元素 while(x < a[j]){ //查找在有序表的插入位置 a[j+dk] = a[j]; j -= dk; //元素后移 } a[j+dk] = x; //插入到正确位置 } print(a, n,i ); } } /** * 先按增量d（n/2,n为要排序数的个数进行希尔排序 * */ void shellSort(int a[], int n){ int dk = n/2; while( dk >= 1 ){ ShellInsertSort(a, n, dk); dk = dk/2; } }
希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于增量因子序列d的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。
增量因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：增量因子中除1 外没有公因子，且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。
3 选择排序—简单选择排序（Simple Selection Sort）
- 思想
在要排序的一组数中，选出最小/大的一个数与第1个位置的数交换
然后在剩下的数当中再找最小/大的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止
- 操作
第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；
第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；
以此类推…
第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，
直到整个序列按关键码有序。
- 实现
/** * 数组的最小值 * * @return int 数组的键值 */ int SelectMinKey(int a[], int n, int i) { int k = i; for(int j=i+1 ;j< n; ++j) { if(a[k] > a[j]) k = j; } return k; } /** * 选择排序 * */ void selectSort(int a[], int n){ int key, tmp; for(int i = 0; i< n; ++i) { key = SelectMinKey(a, n,i); //选择最小的元素 if(key != i){ tmp = a[i]; a[i] = a[key]; a[key] = tmp; //最小元素与第i位置元素互换 } print(a, n , 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元素重新建成堆的调整过程
调整小顶堆
- 设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素
将堆底元素送入堆顶（（最后一个元素与堆顶进行交换），堆被破坏(根结点不满足堆的性质) - 将根结点与左、右子树中较小元素的进行交换
- 若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法2.
- 若与右子树交换，如果右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法2.
- 继续对不满足堆性质的子树进行上述交换操作，直到叶结点，堆被建成
称这个自根结点到叶子结点的调整过程为筛选
再讨论对n 个元素初始建堆的过程
建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。
1）n 个结点的完全二叉树，则最后一个结点是第n / 2个结点的子树
2）筛选从第n / 2个结点为根的子树开始，该子树成为堆。
3）之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。
如图建堆初始过程：无序序列：（49，38，65，97，76，13，27，49）
- 算法的实现
package com.sss; import java.util.Arrays; /** * @author Shusheng Shi */ public class HeapSort { public static void heapSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int i = 0; i < arr.length; i++) { heapInsert(arr, i); } int size = arr.length; swap(arr, 0, --size); while (size > 0) { heapify(arr, 0, size); swap(arr, 0, --size); } } public static void heapInsert(int[] arr, int index) { while (arr[index] > arr[(index - 1) / 2]) { swap(arr, index, (index - 1) / 2); index = (index - 1) / 2; } } public static void heapify(int[] arr, int index, int size) { int left = index * 2 + 1; while (left < size) { int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left; largest = arr[largest] > arr[index] ? largest : index; if (largest == index) { break; } swap(arr, largest, index); index = largest; left = index * 2 + 1; } } public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } // for test public static void comparator(int[] arr) { Arrays.sort(arr); } // for test public static int[] generateRandomArray(int maxSize, int maxValue) { int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } // for test public static int[] copyArray(int[] arr) { if (arr == null) { return null; } int[] res = new int[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } // for test public static boolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { return false; } if (arr1 == null && arr2 == null) { return true; } if (arr1.length != arr2.length) { return false; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { return false; } } return true; } // for test public static void printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // for test public static void main(String[] args) { int testTime = 500000; int maxSize = 100; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); heapSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { succeed = false; break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); heapSort(arr); printArray(arr); } }
从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置
所以堆排序有两个函数组成
- 一是建堆的渗透函数
- 二是反复调用渗透函数实现排序的函数
void print(int a[], int n){ for(int j= 0; j<n; j++){ cout<<a[j] <<" "; } cout<<endl; } /** * 已知H[s…m]除了H[s] 外均满足堆的定义 * 调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选, * * @param H是待调整的堆数组 * @param s是待调整的数组元素的位置 * @param length是数组的长度 * */ void HeapAdjust(int H[],int s, int length) { int tmp = H[s]; int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置) while (child < length) { if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点) ++child ; } if(H[s]<H[child]) { // 如果较大的子结点大于父结点 H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点 s = child; // 重新设置s ,即待调整的下一个结点的位置 child = 2*s+1; } else { // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出 break; } H[s] = tmp; // 当前待调整的结点放到比其大的孩子结点位置上 } print(H,length); } /** * 初始堆进行调整 * 将H[0..length-1]建成堆 * 调整完之后第一个元素是序列的最小的元素 */ void BuildingHeap(int H[], int length) { //最后一个有孩子的节点的位置 i= (length -1) / 2 for (int i = (length -1) / 2 ; i >= 0; --i) HeapAdjust(H,i,length); } /** * 堆排序算法 */ void HeapSort(int H[],int length) { //初始堆 BuildingHeap(H, length); //从最后一个元素开始对序列进行调整 for (int i = length - 1; i > 0; --i) { //交换堆顶元素H[0]和堆中最后一个元素 int temp = H[i]; H[i] = H[0]; H[0] = temp; //每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整 HeapAdjust(H,0,i); } } int main(){ int H[10] = {3,1,5,7,2,4,9,6,10,8}; cout<<"初始值："; print(H,10); HeapSort(H,10); //selectSort(a, 8); cout<<"结果："; print(H,10); }
分析:
- 设树深度为k
从根到叶的筛选，元素比较次数至多2(k-1)次，交换记录至多k次
所以，在建好堆后，排序过程中的筛选次数不超过下式
建堆时的比较次数不超过4n 次，因此堆排序最坏情况下，时间复杂度也为：
O(nlogn )
5 交换排序—冒泡排序（Bubble Sort）
- 思想
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
##算法的实现
package com.sss; import java.util.Arrays; /** * @author Shusheng Shi */ public class BubbleSort { public static void bubbleSort(int[] arr) { if (arr == null || arr.length < 2) { return; } for (int e = arr.length - 1; e > 0; e--) { for (int i = 0; i < e; i++) { if (arr[i] > arr[i + 1]) { swap(arr, i, i + 1); } } } } public static void swap(int[] arr, int i, int j) { arr[i] = arr[i] ^ arr[j]; arr[j] = arr[i] ^ arr[j]; arr[i] = arr[i] ^ arr[j]; } // for test public static void comparator(int[] arr) { Arrays.sort(arr); } // for test public static int[] generateRandomArray(int maxSize, int maxValue) { int[] arr = new int[(int) ((maxSize + 1) * Math.random())]; for (int i = 0; i < arr.length; i++) { arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random()); } return arr; } // for test public static int[] copyArray(int[] arr) { if (arr == null) { return null; } int[] res = new int[arr.length]; for (int i = 0; i < arr.length; i++) { res[i] = arr[i]; } return res; } // for test public static boolean isEqual(int[] arr1, int[] arr2) { if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) { return false; } if (arr1 == null && arr2 == null) { return true; } if (arr1.length != arr2.length) { return false; } for (int i = 0; i < arr1.length; i++) { if (arr1[i] != arr2[i]) { return false; } } return true; } // for test public static void printArray(int[] arr) { if (arr == null) { return; } for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); } // for test public static void main(String[] args) { int testTime = 500000; int maxSize = 100; int maxValue = 100; boolean succeed = true; for (int i = 0; i < testTime; i++) { int[] arr1 = generateRandomArray(maxSize, maxValue); int[] arr2 = copyArray(arr1); bubbleSort(arr1); comparator(arr2); if (!isEqual(arr1, arr2)) { succeed = false; break; } } System.out.println(succeed ? "Nice!" : "Fucking fucked!"); int[] arr = generateRandomArray(maxSize, maxValue); printArray(arr); bubbleSort(arr); printArray(arr); } }
##冒泡排序算法的改进
对冒泡排序常见的改进方法是加入一标志性变量exchange，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。
本文再提供以下两种改进算法：
1．设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。
//
void Bubble_1 ( int r[], int n) { int i= n -1; //初始时,最后位置保持不变 while ( i> 0) { int pos= 0; //每趟开始时,无记录交换 for (int j= 0; j< i; j++) if (r[j]> r[j+1]) { pos= j; //记录交换的位置 int tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp; } i= pos; //为下一趟排序作准备 } }
2．传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。
改进后的算法实现为:
void Bubble_2 ( int r[], int n){ int low = 0; int high= n -1; //设置变量的初始值 int tmp,j; while (low < high) { for (j= low; j< high; ++j) //正向冒泡,找到最大者 if (r[j]> r[j+1]) { tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp; } --high; //修改high值, 前移一位 for ( j=high; j>low; --j) //反向冒泡,找到最小者 if (r[j]<r[j-1]) { tmp = r[j]; r[j]=r[j-1];r[j-1]=tmp; } ++low; //修改low值,后移一位 } }
相邻值相同时不交换情况下,可以保持稳定性!!!
