八、内排序
8.1 排序的概念
1、排序的定义
所谓排序，是整理表中的记录，使之按关键字递增（或递减） 有序排列。
2、内排序和外排序
在排序过程中，若整个表都是放在内存中处理，排序时不涉 及数据的内、外存交换，则称之为内排序；
反之，若排序过程中要进行数据的内、外存交换，则称之为 外排序。
3、内排序的分类
内排序：
基于比较的排序算法：插入排序、交换排序、选择排序、归并排序
不基于比较的排序算法：基数排序
基于比较的内排序算法效率：
(1) 最好的平均时间复杂度为O(nlog2 n)。
(2) 最好情况是排序序列正序，此时的时间复杂度为O(n)。
4、内排序算法的稳定性
如果待排序的表中，存在有多个关键字相同的记录，经过排序后这些 具有相同关键字的记录之间的相对次序保持不变，则称这种排序方法是稳定的。
反之，若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。
5、正序和反序
若待排序的表中元素已按关键字排好序，称此表中元素为正序；
反之，若待排序的表中元素的关键字顺序正好和排好序的顺序相反， 称此表中元素为反序。
有一些排序算法与初始序列的正序或反序有关，另一些排序算法 与初始序列的情况无关。
8.2 插入排序
主要的插入排序方法：
(1) 直接插入排序 (2) 折半插入排序 (3) 希尔排序
8.2.1 直接插入排序
直接插入排序的算法，平均时间复杂度O(n^2)：
public static int[] insertSort(int[] list) {
int first,position;
int temp; //临时存放list[first]
for(first=1;first<list.length;first++) {
if(list[first] < list[first-1]) { //如果list[first]小于左边的有序表最大值
position = first;
temp = list[first];
while(position>0 && list[position-1]>temp) { //找temp的插入位置，将大于它的右移
list[position] = list[position-1];
position--;
}
list[position] = temp;
}
}
return list;
}
8.2.2 折半插入排序
查找采用折半查找方法，称为二分插入排序或折半插入排序。
折半插入排序算法：
void BinInsertSort(RecType R[],int n){
int i,j,low,high,mid;
RecType tmp;
for(i=1;i<n;i++){
if(R[i].key<R[i-1].key){
tmp=R[i];
low=0;hight=i-1;
while(low<=high){
mid=(low+high)/2;
if(tmp.key<R[mid].key)
high=mid-1;
else
low=mid+1;
}
for(j=i-1;j>=high+1;j--)
R[j+1]=R[j];
R[high+1]=temp;
}
}
}
折半插入排序采用折半查找，查找效率提高。但元素移动次数不变，仅仅将分散移动改为集合移动。
8.2.3 希尔排序
将排序序列分为d个组，在各组内进行直接插入排序，递减d=d/2，重复之前步骤，直到d=1。
希尔排序算法，时间复杂度约为O(n^1.3)：
public static void shellSort(int[] arr) {
//增量每次都是/2
for(int step = arr.length/2;step>0;step/=2) {
//从增量那组开始进行插入排序，直至完毕
for(int i=step;i<arr.length;i++) {
int j=i;
int temp = arr[i];
//j-step就是代表与它前一组相同位置的元素
while(j-step>=0 && arr[j-step]>temp) {
arr[j] = arr[j-step];
j=j-step;
}
arr[j]=temp;
}
}
}
8.3 交换排序
两个记录反序时进行交换。
常见的交换排序方法：(1) 冒泡排序 (2) 快速排序
8.3.1 冒泡排序
冒泡排序算法，平均时间复杂度为O(n^2)：
public static void bubbleSort(int[] list) {
int i,j,temp; bool exchange;
for(i = 0; i<list.length; i++){
exchange=false;
for(j=0; j<list.length-i-1; j++) {
if(list[j]>list[j+1]){
temp = list[j];
list[j]=list[j+1];
list[j+1]=temp;
exchange=true;
}
if(exchange==false) return; //若没有交换的，则直接返回。
}
}
}
8.3.2 快速排序
每趟使表的第1个元素放入适当位置（归位），将表一分为二，对 子表按递归方式继续这种划分，直至划分的子表长为0或1（递归出 口）。
快速排序算法：
public static void quickSort(int[] arr,int p,int r) {
if(p<r){
int q = partition(arr,p,r);
//对左半段排序
quickSort(arr,p,q-1);
//对右半段排序
quickSort(arr,q+1,r);
}
}
private static int partition(int arr[],int p,int r) {
int i=p,j=r+1;
int x = arr[p];
int temp;
//将<x的元素交换到左边区域
//将>x的元素交换到右边区域
while(true) {
//找到左边大于x的位置，再找到右边小于x的位置
while(arr[++i]<x && i<r);
while(arr[--j]>x);
if(i>=j)break;
//连个位置上的元素进行交换
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
arr[p] = arr[j];//j的位置刚好是分界点
arr[j] = x;
return j;
}
快速排序的平均时间复杂度为O(nlog2 n)，平均所需栈空间为O(log2 n)。
8.4 选择排序
常见的选择排序方法：(1) 简单选择排序 (2) 堆排序
####8.4.1 简单选择排序
简单选择排序算法：
public static void selectionSort(int[] arr) {
//记录当前趟数的最小值的下标
int pos;
//交换的变量
int temp;
//外层循环控制需要排序的趟数
for(int i=0;i<arr.length-1;i++) {
//新的趟数，将下标赋值为i
pos=i;
//内层循环控制遍历数组的个数并得到最大数的下标
for(int j=i+1;j<arr.length;j++)
if(arr[j]<arr[pos]) {
pos=j;
}
//交换
if(pos!=i){
temp = arr[pos];
arr[pos] = arr[i];
arr[i]=temp;
}
}
}
简单选择排序的最好、最坏和平均时间复杂度为O(n^2)。
####8.4.2 堆排序
1、堆的定义
一个序列R[1..n]，关键字分别为k1、k2、… 、kn。
该序列满足如下性质（简称为堆性质）：
① ki≤k2i 且ki≤k2i+1
② ki≥k2i 且ki≥k2i+1
满足第①种情况的堆称为小根堆，满足第②种情况的堆称为大根堆。
2、堆排序算法设计
堆排序的关键是构造堆，这里采用筛选算法建堆。
所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树， “调整”根节点使整个二叉树也成为一个堆。
堆排序算法：
public static void heapSort(int[] arr) {
int current;
int i;
//建立初始堆
buildHeap(arr);
for(i = arr.length-1; i>0 ; i--) {
current = arr[i];
arr[i] = arr[0];
insertHeap(arr,current,0,i-1);
}
}
private static void insertHeap(int[] arr,int current,int low,int high) {
int large;
large = 2 * low + 1;
while (large <= high) {
if (large < high&&arr[large] < arr[large + 1])
large++;
if (current > arr[large])
break;
else {
arr[low] = arr[large];
low = large;
large = 2 * low + 1;
}
}
arr[low] = current;
}
//建立初始堆
private static void buildHeap(int[] arr){
for(int left = arr.length/2-1 ; left >= 0 ; left--) {
int current = arr[left];
insertHeap(arr,current,left,arr.length-1);
}
}
堆排序的时间复杂度为O(nlog n)，空间复杂度为O(1)，不稳定。
简单选择排序算法→(利用了连续多次查找最大记录的特性)→堆排序算法
8.5 归并排序
1、归并的思路
归并排序是多次将相邻两个或两个以上的有序表合并成一个 新的有序表。
最简单的归并是将相邻两个有序的子表合并成一个有序的表， 即二路归并排序
二路归并算法：
//归并排序
public static void mergeSort(int[] arr,int left,int right) {
//如果数组长度为1，直接返回
if(left==right) return;
//取中间数，进行拆分
int mid=(left+right)/2;
//左边的数不断进行拆分
mergeSort(arr,left,mid);
//右边的数不断进行拆分
mergeSort(arr,mid+1,right);
//合并
merge(arr,left,mid+1,right);
}
//合并数组
private static void merge(int[] arr,int l,int m,int r) {
//左边数组的大小
int[] leftArray = new int[m-l];
//右边数组的大小
int[] rightArray = new int[r-m+1];
//向两个数组里添加元素
for(int i=l;i<m;i++)
leftArray[i-l]=arr[i];
for(int i=m;i<=r;i++)
rightArray[i-m]=arr[i];
int i=0,j=0;
//传入数组arr的第一个元素
int k=l;
//比较这两个数组的值，哪个小，就往数组上放
while(i<leftArray.length && j<rightArray.length) {
//将较小的数放入数组
if(leftArray[i] <= rightArray[j]) {
arr[k] = leftArray[i];
i++; k++;
}else {
arr[k] = rightArray[j];
j++; k++;
}
}
//将左边数组剩余的数放入大数组
while(i<leftArray.length)
arr[k++]=leftArray[i++];
//将右边数组剩余的数放入大数组
while(j<rightArray.length)
arr[k++]=rightArray[j++];
}
二路归并排序的时间复杂度为O(nlog2 n)，空间复杂度为O(n)。
8.6 基数排序
1、基数排序的概念
基数r：对于二进制数r为2，对于十进制数r为10。
2、基数排序的分类
基数排序有两种：最低位优先（LSD）和最高位优先（MSD）。
过程：
(1) 分配：把各个队列置为空队列，然后考察线性表中的每一个节点，将其放入相应队列中。
(2) 收集：按队列的顺序，将各个队列中的节点收尾相接，得到新的节点序列。
由于数据需要放入队列，又要从队列取出来，下需要大量元素移动。所以排序数据和队列均采用链表存储更好。
基数排序是通过”分配”和”收集”过程来实现排序，不需要关键字的比较。
3、基数排序算法
//数组实现
public static void radixSort(int[] arr) {
int max = findMax(arr,0,arr.length-1);
//需要遍历的次数由数组最大值的位数来决定
for(int i=1;max/i>0; i = i* 10){
int[][] buckets = new int[arr.length][10];
//获取每一位数字(个、十、百...)
for(int j=0;j<arr.length;j++) {
int num = (arr[j/i])%10;
//将其放入桶子里
buckets[j][num] = arr[j];
}
//回收桶子里的元素
int k = 0;
//有10个桶子
for(int j=0;j<10;j++) {
//对每个桶子里的元素进行回收
for(int l=0;l<arr.length;l++) {
//如果桶子里面有元素就回收（数据初始化为0）
if(buckets[l][j]!=0) {
arr[k++] = buckets[l][j];
}
}
}
}
}
//找数组中最大元素
public static int findMax(int[] arr,int l,int r) {
//如果该数组只有一个数，那么对打的就是该数组第一个值了
if(l == r) return arr[l];
int a = arr[l];
int b = findMax(arr, l+1, r);//找出整体的最大值
if(a>b) return a;
else return b;
}
基数排序的时间复杂度为O(d(n+r))，空间复杂度为O(r)。
8.7 各种内排序的比较
1、按算法平均时间复杂度分类
(1) 平方阶O(n^2)：直接插入、简单选择、冒泡排序
(2) 线性对数阶O(nlog2 n)：快速排序、堆排序。归并排序
(3) 线性阶O(n)：基数排序
2、按算法空间复杂度分类
(1) O(n)：归并排序，基数排序为O(r)
(2) O(log2 n)：快速排序
(3) O(1)：其他排序方法
3、按算法稳定性分类
(1) 不稳定的：希尔排序、快速排序、堆排序、简单选择排序
(2) 稳定的：其他排序包括 冒泡、插入、归并、基数是稳定的
4、如何选择合适的排序算法
因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素：
- 待排序的元素数目n（问题规模）；
- 元素的大小（每个元素的规模）；
- 关键字的结构及其初始状态；
- 对稳定性的要求；
- 语言工具的条件；
- 排序数据的存储结构；
- 时间和辅助空间复杂度。
详细内容和总结见PPT。