简介
- 定义:
- 假设有n个记录的序列为{r1,r2,…,rn}, 其相应的关键字分别为{k1,k2,…,kn}, 需确定1,2,…,n的一种排列p1,p2,…,pn, 使其相应的关键字满足k_p1 <= k_p2 <= … <= k_pn (非递减或非递增)关系, 即使得序列成为一个按关键字 有序的序列{r_p1,r_p2,…,r_pn}, 这样的操作就称为排序
- 说明:
- 排序可以看成是线性表的一种操作
- 排序的依据是关键字之间的大小关系
- 组合排序可以将主关键字与次关键字拼成字符串, 转化成单关键字排序
排序的稳定性
- 假设ki=kj (1<=i<=n, 1<=j<=n, i<>j), 且在排序前的序列中ri领先与rj (i<j)。如果排序后ri仍领先rj, 则称所用的排序方法是稳定的; 反之, 若可能使得排序后rj领先ri, 则称所用排序方法是不稳定的。
内排序与外排序
内排序
- 概述: 在排序的整个过程中, 待排序的所有记录全部被放置在内存中
- 性能影响:
- 时间性能: 比较和移动操作尽量少
- 辅助空间
- 算法的复杂性: 算法本身的复杂度, 非算法的时间复杂度
- 分类:
- 插入排序: 直接插入排序和希尔排序
- 交换排序: 冒泡排序和快速排序
- 选择排序: 简单选择排序和堆排序
- 归并排序: 归并排序
外排序
- 概述: 由于排序的记录个数太多, 不能同时放置在内存, 整个排序过程需要在内外存之间多次交换数据才能进行
七种排序算法
- 简单算法: 冒泡排序, 简单选择排序, 直接插入排序
- 改进算法: 希尔排序, 堆排序, 归并排序和快速排序
冒泡排序(Bubble Sort)
- 基本思想: 两两比较相邻记录的关键字, 如果反序则交换, 知道没有反序的记录为止
- 优化:
- 增加标记变量flag初始值为true, 进入第一层循环后为false, 第二层循环若有数据交换则为false, 判断第一层循环为false则退出
- 复杂度:
- 特点: 稳定
实现
public class BubbleSort {
/**
* 普通冒泡排序
* @param arr
* @return
*/
static int[] bubbleSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
for (int j = arr.length - 1; j >= i; j--) {
if (arr[j] < arr[j - 1]) {
Utils.swap(arr, j, j - 1);
}
System.out.println("排序中: " + Arrays.toString(arr));
}
}
return arr;
}
/**
* 优化冒泡排序, 没有任何数据交换则说明有序
* @param arr
* @return
*/
static int[] bubbleSortOp(int[] arr) {
boolean flag = true;
for (int i = 1; i < arr.length && flag; i++) {
flag = false;
for (int j = arr.length - 1; j >= i; j--) {
if (arr[j] < arr[j - 1]) {
Utils.swap(arr, j, j - 1);
flag = true;
}
System.out.println("排序中: " + Arrays.toString(arr));
}
}
return arr;
}
}
简单选择排序(Simple Selection Sort)
- 基本思想:
- 通过n-i次关键字间的比较, 从n-i+1个记录中选出关键字最小的记录, 并和第i(1<=i<=n)个记录交换之
- 复杂度:
- 特点:
- 稳定
- 减少了移动操作次数, 性能略优于冒泡排序
- 无论最好与最差情况, 比较次数都一样的多
实现
public class SelectSort {
static int[] simpleSelectSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
int minIndex = i; //记录最小的角标
for (int j = i + 1; j < arr.length; j++) {
if(arr[minIndex] > arr[j]){
minIndex = j;
}
}
//相比冒泡减少了元素交换的操作次数
if (minIndex != i){ //找到本次最小的角标, 则交换
Utils.swap(arr, minIndex, i);
}
}
return arr;
}
}
直接插入排序(Straight Insert Sort)
- 基本思想:
- 将一个记录插入到已经排好序的有序表中, 从而得到一个新的, 记录数增1的有序表
- 复杂度:
- 特点:
实现
public class InsertSort {
static int[] straightInsertSort(int[] arr) {
if (arr == null || arr.length == 0) {
return arr;
}
for (int i = 1; i < arr.length; i++) {
if (arr[i] < arr[i - 1]) {
int j = i;
int tmp = arr[i];
while (j > 0 && tmp < arr[j - 1]) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = tmp;
}
}
return arr;
}
}
// 5 3 4 6 2 j=i=1 tmp=3
// 5 5 4 6 2 j=i=1 tmp=3
// 3 5 4 6 2 i=1 j=0 tmp=3
// 3 5 4 6 2 j=i=2 tmp=4
// 3 5 5 6 2 i=2 j=1 tmp=4>arr[0]=3
// 3 4 5 6 2 i=3 arr[3]=6>arr[2]=5
// 3 4 5 6 2 j=i=4 tmp=2
// 3 4 5 6 6 i=4 j=3 tmp=2<arr[2]=5
// 3 4 5 5 6 i=4 j=2 tmp=2<arr[1]=4
// 3 4 4 5 6 i=4 j=1 tmp=2<arr[0]=3
// 3 3 4 5 6 i=4 j=0 tmp=2
// 2 3 4 5 6 i=4 j=0 tmp=2
希尔排序(Shell Sort)
- 相关概念:
- 基本有序: 小的关键字基本在前面, 大的基本在后面, 不大不小的基本在中间
- 跳跃分割策略: 将相距某个"增量"的记录组成一个子序列, 这样才能保证在子序列内分别进行直接插入排序后得到的结果的是基本有序而不是局部有序
- 基本思想:
- 先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时再对全体记录进行一次直接插入排序
- 复杂度:
- 时间复杂度: O(nlogn) ~ O(n^2)
- 时间复杂度是所取增量的函数
- 最好: 在大量实验的基础上推出当n在某个范围内时，时间复杂度可以达到O(n^1.3)
- 最坏: O(n^2)
- 空间复杂度: O(1)
- 特点: 不稳定
实现
public class ShellSort {
static int[] shellSort(int[] arr) {
int increment = arr.length;
do {
increment = increment/3 +1; //跳跃分割间隔
for (int i = increment; i < arr.length; i++) {
int j = i;
int tmp = arr[i];
while (j > increment - 1 && tmp < arr[j - increment]){
arr[j] = arr[j - increment];
j -= increment;
}
arr[j] = tmp;
}
} while (increment > 1);
return arr;
}
}
堆排序(Heap Sort)
- 堆结构:
- 具有以下性质的完全二叉树:
- 每个结点的值都大于或等于其左右孩子结点的值, 称为 大顶堆(arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] ); 或者每个结点的值都小于或等于其左右孩子结点的值, 称为 小顶堆(arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2])
- 如果它有左子树，那么左子树的位置是2i+1，如果有右子树，右子树的位置是2i+2，如果有父节点，父节点的位置是(n-1)/2取整。分为最大堆和最小堆，最大堆的任意子树根节点不小于任意子结点，最小堆的根节点不大于任意子结点
- 基本思想:
- 将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
- 复杂度:
- 时间复杂度: O(nlogn)
- 构建堆的时间复杂度为O(n)
- 第i次取堆顶记录重建堆需要O(logi)的时间(完全二叉树的某个结点到根节点的距离为[log2(i)] + 1)
- 最好: O(nlogn)
- 最坏: O(nlogn)
- 空间复杂度: O(1)
- 特点:
实现
public class HeapSort {
static int[] heapSort(int[] arr){
//1.构建大顶堆
for (int i = arr.length/2 - 1; i >= 0; i--) {
heapAdjust(arr, i, arr.length - 1);
System.out.println("大顶堆1: " + Arrays.toString(arr));
}
//2. 交换堆顶元素与末尾元素, 调整堆结构
for (int i = arr.length - 1; i > 0; i--) {
//交换堆顶记录和当前未排序子序列的最后一个记录
Utils.swap(arr, 0, i);
//将arr[0, 1, ..., i -1]重新调整为大顶堆
heapAdjust(arr, 0, i - 1);
System.out.println("大顶堆2: " + Arrays.toString(arr));
}
return arr;
}
private static void heapAdjust(int[] arr, int s, int len){
int tmp = arr[s]; //暂存最大结点
for (int i = s*2 + 1; i < len; i = i*2 + 1) { //从s的左孩子结点(2s+1)开始比较
if (i < len && arr[i] < arr[i + 1]){ //i为关键字中记录最大的下标
i ++;
}
if (tmp >= arr[i]){
break;
}
arr[s] = arr[i];
s = i;
}
arr[s] = tmp;
}
}
// arr[] = {50, 10, 90, 30, 70, 40, 80, 60, 20}
// 50
// / \
// 10 90
// / \ / \
// 30 70 40 80
// / \
// 60 20
//1.构建大顶堆
// 第三排
// 30 60
// / \ / \
// 60 20 30 20
// 第二排
// 90
// / \
// 40 80 40<80
// 第二排
// 10
// / \
// 60 70 60<70
// 70
// / \
// 60 10
// 第一排
// 50 90
// / \ / \
// 70 90 70<90 70 90
// 第二排
// 90 80 80
// / \ / \ / \
// 40 80 40<80 40 80 40 50
//结果
// arr[] = {90, 70, 80, 60, 10, 40, 50, 30, 20}
// 90
// / \
// 70 80
// / \ / \
// 60 10 40 50
// / \
// 30 20
//2. 交换堆顶元素与末尾元素, 调整堆结构
//arr[] = {80, 70, 50, 60, 10, 40, 20, 30, 90}
//arr[] = {70, 60, 50, 30, 10, 40, 20, 80, 90}
//arr[] = {60, 30, 50, 20, 10, 40, 70, 80, 90}
//arr[] = {50, 30, 40, 20, 10, 60, 70, 80, 90}
//arr[] = {40, 30, 10, 20, 50, 60, 70, 80, 90}
//arr[] = {30, 20, 10, 40, 50, 60, 70, 80, 90}
//arr[] = {20, 10, 30, 40, 50, 60, 70, 80, 90}
//arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90}
归并排序(Merging Sort)
- 基本思想:
- 将待排序序列R[0…n-1]看成是n个长度为1的有序序列, 将相邻的有序表成对归并, 得到n/2个长度为2的有序表; 将这些有序序列再次归并, 得到n/4个长度为4的有序序列; 如此反复进行下去, 最后得到一个长度为n的有序序列。这种排序方法称为2路归并排序。
- 复杂度:
- 时间复杂度: O(nlogn)
- 空间复杂度: 递归方法( O(n + logn) ), 非递归方法( O(n) )
- 特点:
实现
public class MergeSort {
/**
* 递归实现
* @param arr
* @param left
* @param right
* @return
*/
static int[] sortByRecursion(int[] arr, int left, int right) {
int mid = (left + right) / 2;
if (left < right) {
//左边
sortByRecursion(arr, left, mid);
//右边
sortByRecursion(arr, mid + 1, right);
//左右归并
merge(arr, left, mid, right);
System.out.println("排序中: " + Arrays.toString(arr));
}
return arr;
}
private static void merge(int[] arr, int left, int mid, int right) {
int tmp[] = new int[right - left + 1];
int i = left, j = mid + 1; //左右指针
int k = 0; // 合并后数组的指针
//将较小的数移动到tmp中
while (i <= mid && j <= right) {
if (arr[i] < arr[j]) {
tmp[k++] = arr[i++];
} else {
tmp[k++] = arr[j++];
}
}
//将左边剩余的数组移入tmp
while (i <= mid) {
tmp[k++] = arr[i++];
}
//将右边剩余数组移入tmp
while (j <= right) {
tmp[k++] = arr[j++];
}
//将数据复制会原数组
for (int l = 0; l < tmp.length; l++) {
arr[l + left] = tmp[l];
}
}
/**
* 使用迭代代替递归
* @param arr
* @return
*/
static int[] sort(int[] arr) {
int len = arr.length;
int k = 1;
while (k < len) {
mergePass(arr, k, len);
k *= 2;
}
return arr;
}
private static void mergePass(int[] arr, int k, int n) {
int i = 0;
//从前往后,将2个长度为k的子序列合并为1个
while (i < n - 2 * k + 1) {
merge(arr, i, i + k - 1, i + 2 * k - 1);
i += 2 * k;
}
//将那些“落单的”长度不足两两merge的部分和前面merge起来。
if (i < n - k) {
merge(arr, i, i + k - 1, n - 1);
}
}
}
// arr[] = {50, 10, 90, 30, 70, 40, 80, 60, 20}
// 递归
//{50, 10, 90, 30, 70}
//{50, 10, 90}
//{50, 10} {10, 50}
//{90}
//{10, 50, 90}
//{30, 70}
//{10, 30, 50, 70, 90}
//{40, 80, 60, 20}
//{40, 80}
//{60, 20} {20, 60}
//{20, 40, 60, 80}
//{10, 20, 30, 40, 50, 60, 70, 80, 90}
// 迭代
// k = 1
//merge(arr, 0, 0, 1)
//{50, 10} {10, 50}
//merge(arr, 2, 2, 3)
//{90, 30} {30, 90}
//merge(arr, 4, 4, 5)
//{70, 40} {40, 70}
//merge(arr, 6, 6, 7)
//{80, 60} {60, 80}
//{20}
//{10, 50, 30, 90, 40, 70, 60, 80, 20}
// k= 2
//merge(arr, 0, 1, 3)
//{10, 50, 30, 90} {10, 30, 50, 90}
//merge(arr, 4, 5, 7)
//{40, 70, 60, 80} {40, 60, 70, 80}
//{10, 30, 50, 90, 40, 60, 70, 80, 20}
// k = 4
//merge(arr, 0, 3, 7)
//{10, 30, 50, 90, 40, 60, 70, 80} {10, 30, 40, 50, 60, 70, 80, 90}
//{10, 30, 40, 50, 60, 70, 80, 90, 20}
// k = 8
//merge(arr, 0, 7, 8)
//{10, 30, 40, 50, 60, 70, 80, 90, 20} {10, 20, 30, 40, 50, 60, 70, 80, 90}
快速排序(Quick Sort)
- 相关概念:
- 枢纽(pivot): 选取其中一个关键字, 将它放到一个位置, 使得它左边的值都比它小, 右边的值比它大
- 基本思想: 基于分治的思想，是冒泡排序的改进型
- 首先在数组中选择一个基准点（该基准点的选取可能影响快速排序的效率），然后分别从数组的两端扫描数组，设两个指示标志（low指向起始位置，high指向末尾);
- 循环从后半部分开始，如果发现有元素比该基准点的值小，就交换low和high位置的值
- 循环从前半部分开始扫秒，发现有元素大于基准点的值，就交换low和high位置的值
- 直到low>=high, 然后把基准点的值放到high这个位置。一次排序就完成了。
- 以后采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组就自然有序了
- 复杂度:
- 时间复杂度: O(nlogn)
- 最优情况: O(nlogn)
- 最差情况: O(n^2)
- 空间复杂度: O(logn) ~ O(n)
- 特点:
优化
- 优化选取枢纽
- 随机选取: 随机获取low与high之间的树rnd
- 三数取中: 取左端, 中间和右端三数, 将中数作为枢纽
- 九数取中: 从数组三次取样, 三个样品中取出中数后再取一个中数作为枢纽
- 优化不必要的交换
- 优化小数组的排序方案
- 优化递归操作: 使用尾递归
实现
public class QuickSort {
static int[] quickSort(int[] arr, int left, int right) {
if (left < right){
int pivotPos = partition(arr, left, right); //将arr[]一分为二
quickSort(arr, left, pivotPos - 1);
quickSort(arr, pivotPos + 1, right);
}
return arr;
}
/**
* 尾递归优化
* @param arr
* @param left
* @param right
* @return
*/
static int[] quickSortOp(int[] arr, int left, int right) {
while (left < right){ //使用while循环
int pivotPos = partition(arr, left, right); //将arr[]一分为二
quickSort(arr, left, pivotPos - 1);
left = pivotPos + 1; //尾递归
}
return arr;
}
private static int partition(int[] arr, int left , int right){
int pivotKey = arr[left]; //用子表的第一个记录作为枢纽
while (left < right) {
while (left < right && pivotKey <= arr[right]){
right --;
}
// Utils.swap(arr, left, right); //右端比枢纽小的交换到左端
arr[left] = arr[right]; //优化1: 把小的移动到左边
while (left < right && pivotKey >= arr[left]){
left ++;
}
// Utils.swap(arr, left, right); //左端比枢纽大的交换到右端
arr[right] = arr[left]; //优化2: 把大的移动到右边
System.out.println("排序中: " + Arrays.toString(arr));
}
arr[left] = pivotKey; //优化3: 最后把pivotKey赋值到中间
return left;
}
}
// arr[] = {50, 10, 90, 30, 70, 40, 80, 60, 20}
//pivotKey=50 right=8 left=0 {20, 10, 90, 30, 70, 40, 80, 60, 50}
//pivotKey=50 left=2 right=8 {20, 10, 50, 30, 70, 40, 80, 60, 90}
//pivotKey=50 right=5 left=2 {20, 10, 40, 30, 70, 50, 80, 60, 90}
//pivotKey=50 left=4 right=5 {20, 10, 40, 30, 50, 70, 80, 60, 90}
//pivotKey=50 right=4 left=4 {20, 10, 40, 30, 50, 70, 80, 60, 90}
//低子表
//pivotPos = 4 quickSort(arr, 0, 3) {20, 10, 40, 30}
//partition(arr, 0, 3)
//pivotKey = 20 right=3 left=0 {20, 10, 40, 30}
//pivotKey = 20 right=1 left=0 {10, 20, 40, 30}
//pivotKey = 20 left=1 right=1 {10, 20, 40, 30}
//pivotPos = 1 quickSort(arr, 0, 0) {10}
//pivotPos = 1 quickSort(arr, 2, 3) {10, 20, | 40, 30}
//partition(arr, 2, 3)
//pivotKey = 40 right=3 left=2 {10, 20, | 30, 40}
//pivotKey = 40 left=3 right=3 {10, 20, | 30, 40}
//pivotPos = 3 quickSort(arr, 2, 2)
//pivotPos = 3 quickSort(arr, 4, 3)
//高子表
//pivotPos = 4 quickSort(arr, 5, 8) {10, 20, 30, 40, 50, | 70, 80, 60, 90}
//partition(arr, 5, 8)
//pivotKey = 70 right=8 left=5 {10, 20, 30, 40, 50, | 70, 80, 60, 90}
//pivotKey = 70 right=7 left=5 {10, 20, 30, 40, 50, | 60, 80, 70, 90}
//pivotKey = 70 left=6 right=7 {10, 20, 30, 40, 50, | 60, 70, 80, 90}
//pivotKey = 70 right=6 left=6 {10, 20, 30, 40, 50, | 60, 70, 80, 90}
//pivotPos = 6 quickSort(arr, 5, 5)
//pivotPos = 6 quickSort(arr, 7, 8) {10, 20, 30, 40, 50, 60, 70, | 80, 90}
//pivotKey = 80 partition(arr, 7, 8) {10, 20, 30, 40, 50, 60, 70, | 80, 90}
//pivotKey = 80 right=7 left=7 {10, 20, 30, 40, 50, 60, 70, | 80, 90}
//pivotPos = 7 quickSort(arr, 7, 6)
//pivotPos = 7 quickSort(arr, 8, 8)
参考