目录
1. 冒泡排序
2. 选择排序
3. 堆排序
4. 插入排序
5.归并排序
6. 快速排序
7. 希尔排序
8. 计数排序
9. 基数排序
10. 桶排序
前言
排序算法的稳定性:
如果相等的2个元素，在排序前后的相对位置保持不变，那么这是稳定的排序算法
排序前：5, 1, 3𝑎, 4, 7, 3𝑏
稳定的排序： 1, 3𝑎, 3𝑏, 4, 5, 7
不稳定的排序：1, 3𝑏, 3𝑎, 4, 5, 7
对自定义对象进行排序时，稳定性会影响最终的排序效果
常见的递推式与复杂度
1. 冒泡排序
思路:
1. 从头开始比较每一对相邻元素，如果第1个比第2个大，就交换它们的位置; 执行完一轮后，最末尾那个元素就是最大的元素
2. 忽略 1 中曾经找到的最大元素，重复执行步骤1，直到全部元素有序
/**
* 冒泡排序(原始版)
* @param array
*/
public static void sort(Integer[] array){
for (int end = array.length - 1; end >= 1 ; end--) {
for (int i = 1; i <= end; i++) {
if(array[i-1] > array[i]){
int tmp = array[i];
array[i] = array[i-1];
array[i-1] = tmp;
}
}
}
}
优化思路1:
在每一次循环开始的时候,将sorted默认置为true, 如果在一次循环结束后, sorted仍然为true, 即在该轮遍历中未触发交换操作, 则认为此时数组已有序, 直接退出排序
/**
* 冒泡排序(优化版1)
* @param array
*/
public static void sort(Integer[] array){
for (int end = array.length - 1; end >= 1 ; end--) {
boolean sorted = true; //在每一次循环开始的时候,将sorted默认置为true, 如果在一次循环结束后, sorted仍然为true, 则认为此时数组已有序, 直接退出排序
for (int i = 1; i <= end; i++) {
if(array[i-1] > array[i]){
int tmp = array[i];
array[i] = array[i-1];
array[i-1] = tmp;
sorted = false;
}
}
if(sorted) break;
}
}
优化思路2:
1.sortedIndex为上一次进行排序交换的位置 (如果sortedIndex在内循环完成一轮比较后,未发生变化, 则说明数组无序排序,直接返回)
2.如果在数组尾部已存在部分数据有序, 那么在下一次循环时将跳过已排好序的部分, 减少比较次数
/**
* 冒泡排序(优化版2)
* @param array
*/
public static void sort(Integer[] array){
for (int end = array.length - 1; end >= 1 ; end--) {
int sortedIndex = 1; //上一次进行排序交换的位置 (如果sortedIndex在内循环完成一轮比较后,未发生变化, 则说明数组无序排序,直接返回)
for (int i = 1; i <= end; i++) {
if(array[i-1] > array[i]){
int tmp = array[i];
array[i] = array[i-1];
array[i-1] = tmp;
sortedIndex = i;
}
}
end = sortedIndex;
}
}
总结:
最坏、平均时间复杂度: O(n^2)
最好时间复杂度: O(n)
空间复杂度: O(1)
2. 选择排序
思路:
1. 从序列中找出最大的那个元素, 然后与最末尾的元素交换位置,执行完一轮后，最末尾的那个元素就是最大的元素
2. 忽略1中曾经找到的最大元素, 重复执行步骤1
/**
* 选择排序
* @param array
*/
public static void sort(Integer[] array){
for(int end = array.length-1; end >= 1; end--){
int maxIndex = 0;//每次循环假设第一个元素为最大元素的下标
for (int i = 1; i <= end; i++) { //找出最大值
if(array[maxIndex] <= array[i]){
maxIndex = i;
}
}
//将最大值替换数组尾部元素
int tmp = array[maxIndex];
array[maxIndex] = array[end];
array[end] = tmp;
}
}
总结:
选择排序的交换次数要远远少于冒泡排序，平均性能优于冒泡排序
最好、最坏、平均时间复杂度：O(n^2)，空间复杂度：O(1)，属于不稳定排序
选择排序为什么是不稳定排序?
在第一轮比较后, 将10与2交换, 这里虽然保证在了 10 与 10 的相对位置, 但是 8 与 8 的相对位置却没有保证, 即在整个排序结束后8 与 8 的相对位置发生了变化, 所以选择排序是不稳定的排序
优化思路: 堆排序
3. 堆排序
堆排序可以认为是对选择排序的一种优化
思路:
1.对序列进行原地建堆(heapify）
2.重复执行以下操作，直到堆的元素数量为 1
(1) 交换堆顶元素与尾元素
(2) 堆的元素数量减1
(3) 对0位置进行1次siftDown操作
public class HeapSort {
private int heapSize;
private Integer[] array;
public HeapSort(Integer[] array){
this.array = array;
}
public void sort(){
//将数组批量建堆
heapSize = array.length;
for (int i = (heapSize >> 1) - 1; i >=0 ; i--) {
siftDown(i);
}
while(heapSize > 0){ //将堆顶元素放在数组末尾,将数组默认元素放在堆顶, 进行下虑,维护堆的性质
-- heapSize;
int tmp = array[0];
array[0] = array[heapSize];
array[heapSize]= tmp;
siftDown(0);
}
}
/**
* 堆的下虑操作
* @param index
*/
private void siftDown(int index) {
Integer element = array[index];
int half = heapSize >> 1;
while (index < half) { // index必须是非叶子节点
// 默认是左边跟父节点比
int childIndex = (index << 1) + 1;
Integer child = array[childIndex];
int rightIndex = childIndex + 1;
// 右子节点比左子节点大
if (rightIndex < heapSize && array[rightIndex]> child) {
child = array[childIndex = rightIndex];
}
// 大于等于子节点
if (element>= child) break;
array[index] = child;
index = childIndex;
}
array[index] = element;
}
public static void main(String[] args) {
Integer[] array = Integers.random(10, 1, 50);
Integers.println(array);
new HeapSort(array).sort();
Integers.println(array);
}
}
4. 插入排序
思路:
1. 在执行过程中，插入排序会将序列分为2部分
头部是已经排好序的，尾部是待排序的
2. 从头开始扫描每一个元素
每当扫描到一个元素，就将它插入到头部合适的位置，使得头部数据依然保持有序
/**
* 插入排序
*/
public void sort1() {
for (int begin = 1; begin < array.length; begin++) {
int cur = begin;
while (cur > 0 && array[cur] < array[cur - 1]) { //依次向前交换数据, 直至找到合适的位置
int tmp = array[cur];
array[cur] = array[cur-1];
array[cur-1] = tmp;
cur--;
}
}
}
优化思路1: 减少元素交换次数
1. 先将待插入的元素备份
2. 头部有序数据中比待插入元素大的，都朝尾部方向挪动1个位置
3. 将待插入元素放到最终的合适位置
/**
* 插入排序优化: 减少元素交换次数
*/
public void sort2() {
for (int begin = 1; begin < array.length; begin++) {
int cur = begin; //[0,begin)为有序数据
int v = array[cur]; //暂存目标数据,
while (cur > 0 && array[cur] < array[cur - 1]) { //依次将前一个值向后挪动, 直至使得[0,begin]这个区间的数据恢复有序
array[cur] = array[cur - 1];
cur--;
}
array[cur] = v; //将目标数据放在数组中合适的位置
}
}
优化思路2: 引入二叉搜索, 查找目标数据将要插入的位置(由于区域中第一个大于目标数据的元素索引位置)
二分查找:
/**
* 二分查找
* 注意:
* 当start与end指针所指的索引是近邻的两个数时, start和end的索引和除以2计算出mid的值(int类型)一定等于start,
* 由于目标数字在start和end范围内, 那么如果目标数字与start索引位置的数字不相等, 那么最后start将与end指向同一个数字,
* 因为目标数字与mid所指的数字比较后, 再次更新start值时, 使用的是mid+1, 那么start将与end指向同一个数字
*/
public int binarySearch(Integer[] array, int target){
int start = 0;
int end = array.length - 1;
while(start <= end){ //必须为start<=end, 否则当查找到start与end为数组中相邻的两个数值后,无法在进行判断
int mid = (start + end) >> 1;
if(target < array[mid]){ //目标值在[start,mid)中
end = mid - 1; //更新end, 因为mid已经确定不是目标数据的索引, 所以直接更新为mid的前一个索引
}else if(target > array[mid]){//目标值在(mid,end]中
start = mid + 1; //更新start, 因为mid已经确定不是目标数据的索引, 所以直接更新为mid的后一个索引
}else{
return mid; //找到目标数据, 返回索引
}
}
return -1; //没有找到, 返回-1;
}
基于二分查找优化
public class InsertionSort {
private Integer[] array;
public InsertionSort(Integer[] array){
this.array = array;
}
/**
* 改造版二叉搜索, 查找后返回的值是数组中大于目标值最小值的索引
* 注意:
* 当start与end指针所指的索引是近邻的两个数时, start和end的索引和除以2计算出mid的值(int类型)一定等于start,
* 由于目标数字在start和end范围内, 那么如果目标数字与start索引位置的数字不相等, 那么最后start将与end指向同一个数字,
* 因为目标数字与mid所指的数字比较后, 再次更新start值时, 使用的是mid+1, 那么start将与end指向同一个数字
*/
public int binarySearch(int index){
int start = 0; //数组中有序范围的第一个索引位置
int end = index; //数组中有序范围的最后一个索引后面的位置, 即有序范围是:[start,end)
while(start < end){ //每一次循环需要保证有序范围是:[start,end)
int mid = (start + end) >> 1; //获取中间索引
if(array[index] < array[mid]){ //目标值在[start,mid)中
end = mid;
}else if(array[index] > array[mid]){//目标值在[mid,end)中
start = mid + 1;
}
}
return start;
}
public void sort(){
//遍历数组中所有的元素, 对每个元素寻找合适的位置进行插入
for (int begin = 1; begin < array.length; begin++) {
int target = array[begin]; //目标数据
int dest = binarySearch(begin); //查找到目标数据的合适位置
for (int i = begin; i > dest; i--) { //挪动合适位置之后的数据
array[i] = array[i - 1];
}
array[dest] = target;
}
}
public static void main(String[] args) {
Integer[] array = {7,89,45,6,123,3,12,1};
Integers.println(array);
new InsertionSort(array).sort();
Integers.println(array);
}
}
需要注意的是，使用了二分搜索后，只是减少了比较次数，但插入排序的平均时间复杂度依然是 O(n^2)
5.归并排序
思路:
1. 不断地将当前序列平均分割成2个子序列, 直到不能再分割(序列中只剩1个元素)
2. 不断地将2个子序列合并成一个有序序列, 直到最终只剩下1个有序序列 (在合并的过程中对两个有序子序列进行归并排序)
归并细节:
需要 merge 的 2 组序列存在于同一个数组中，并且是挨在一起的
为了更好地完成 merge 操作，最好将其中 1 组序列备份出来，比如 [begin, mid)
归并过程(1)
归并过程(2) -- 左边数组先结束
归并过程(3) -- 右边数组先结束
public class MergeSort {
private Integer[] leftArray; //备份左侧数组的数据
Integer[] array;
public MergeSort(Integer[] array) {
this.array = array;
}
public void sort(){
leftArray = new Integer[array.length >> 1]; //初始化数组
sort(0,array.length);
}
/**
* 对 [begin, end) 范围的数据进行归并排序
*/
public void sort(int begin, int end){
/**
* 分割数组, 对分割出来的子序列进行排序
*/
if(end - begin < 2) return ;
int mid = (begin + end)/2;
sort(begin, mid); //左侧数组排序
sort(mid, end); //右侧数组排序
/**
* 将左右子序列进行排序
*/
merge(begin, mid, end);
}
public void merge(int begin, int mid, int end) {
int li = 0, le = mid - begin;
int ri = mid, re = end;
int ai = begin;
//备份左侧数组
for(int i = li; i < le; i++){
leftArray[i] = array[begin + i];
}
//如果左边数组还没排序完, 一旦左边排序完成, 那么数组即排序完成 (左右子序列均为有序)
while(li < le){
if(ri < re && array[ri] < leftArray[li] ){ //右侧子序列未排序完成且右侧数据小
array[ai] = array[ri];
ai ++;
ri ++;
}else{ //右侧子序列排序完成 或者 左侧数据小
array[ai] = leftArray[li];
ai ++;
li ++;
}
}
}
public static void main(String[] args) {
Integer[] array = {7,89,45,6,123,3,12,1};
Integers.println(array);
new MergeSort(array).sort();
Integers.println(array);
}
}
总结:
6. 快速排序
思路:
1. 从序列中选择一个轴点元素(pivot)
假设每次选择0位置的元素为轴点元素
2. 利用 pivot 将序列分割成2个子序列
a. 将小于 pivot 的元素放在pivot前面(左侧)
b. 将大于 pivot 的元素放在pivot后面(右侧)
c. 等于pivot的元素放哪边都可以
3. 对子序列进行1,2操作
直到不能再分割(子序列中只剩下1个元素)
快速排序的本质: 逐渐将每一个元素都转换成轴点元素
快速排序流程:
获取轴点元素位置:
1. 假设begin位置的元素为轴点元素并备份轴点元素
2. 比较end位置元素与轴点元素的大小
2.1 如果大于轴点元素, 则end指针向前移动; begin指针保持不变, 继续步骤2
2.2 如果小于等于轴点元素, 则将当前元素移动到begin位置; begin指针向后移动,end指针保持不变,继续步骤3 (此时end位置元素已备份至begin位置)
3. 比较begin位置元素与轴点元素的大小
3.1 如果小于轴点元素, 则begin指针向后移动; end指针保持不变, 继续步骤3
3.2 如果大于等于轴点元素, 则将当前元素移动到end位置; end指针向前移动,begin指针保持不变,继续步骤2 (此时begin位置元素已备份至end位置)
4. 在步骤2,3中如果begin指针与end指针指向同一位置, 表示已获取到当前轴点元素的合适位置(左边元素小于轴点元素,右边元素大于轴点元素)
public class QuickSort {
private Integer[] array;
public QuickSort(Integer[] array) {
this.array = array;
}
public void sort(){
sort(0,array.length);
}
public void sort(int begin, int end){
if (end - begin < 2) return;
// 确定轴点位置 O(n)
int mid = pivotIndex(begin, end); //获取轴点元素的索引
// 对子序列进行快速排序
sort(begin, mid);
sort(mid + 1, end);
}
/**
* 构造出 [begin, end) 范围的轴点元素
* @return 轴点元素的最终位置
*/
private int pivotIndex(int begin, int end) {
// 随机选择一个元素跟begin位置进行交换
swap(begin, begin + (int)(Math.random() * (end - begin)));
// 备份begin位置的元素(轴点元素)
Integer pivot = array[begin];
//end指向最后一个元素
end --;
while(begin < end){
while(begin < end){
if(array[end] > pivot){ // 右边元素 > 轴点元素
end --;
}else{ // 右边元素 <= 轴点元素
array[begin++] = array[end];
break;
}
}
while(begin < end){
if(array[begin] < pivot){ // 左边元素 < 轴点元素
begin ++;
}else{ // 左边元素 >= 轴点元素
array[end--] = array[begin];
break;
}
}
}
// 将轴点元素放入最终的位置
array[begin] = pivot;
return begin;
}
public static void main(String[] args) {
Integer[] array = {7,89,45,6,123,3,12,1};
Integers.println(array);
new QuickSort(array).sort();
Integers.println(array);
}
}
(1) 如果在判断当前元素与轴点元素大小时, 如果当前元素大小等于轴点元素, 采取的措施为保持原位置不变, 那么将会出现什么问题?
将导致轴点元素分割出来的子序列极度不均匀, 导致出现最坏时间复杂度
(2) 如果在判断当前元素与轴点元素大小时, 如果当前元素大小等于轴点元素, 采取的措施为将其移动到begin或者end位置上, 那么将出现什么情况?
7. 希尔排序
思路:
希尔排序把序列看作是一个矩阵，分成𝑚列，逐列进行排序
(1) 𝑚从某个整数逐渐减为1
(2) 当𝑚为1时,整个序列将完全有序
因此，希尔排序也被称为递减增量排序(Diminishing Increment Sort)
矩阵的列数取决于步长序列(step sequence)
比如，如果步长序列为{1,5,19,41,109,...}，就代表依次分成109列、41列、19列、5列、1列进行排序, 不同的步长序列，执行效率也不同
流程:
1. 希尔本人给出的步长序列是 𝑛/2𝑘，比如 𝑛 为16时，步长序列是{1, 2, 4, 8}
2. 分成8列进行排序
3. 分成4列进行排序
4. 分成2列进行排序
5. 分成1列进行排序
特殊场景: 假设有11个元素，步长序列是{1, 2, 5}
假设元素在第 col 列、第 row 行，步长（总列数）是 step
那么这个元素在数组中的索引是 col + row * step
比如 9 在排序前是第 2 列、第 0 行，那么它排序前的索引是 2 + 0 * 5 = 2
比如 4 在排序前是第 2 列、第 1 行，那么它排序前的索引是 2 + 1 * 5 = 7
public class ShellSort {
private Integer[] array;
protected void sort() {
List<Integer> stepSequence = sedgewickStepSequence();
for (Integer step : stepSequence) {
sort(step);
}
}
/**
* 分成step列进行排序
*/
private void sort(int step) {
//循环每一列进行排序
for (int col = 0; col < array.length; col++) {
//插入排序
for (int begin = col + step; begin < array.length; begin += step) {
int cur = begin;
while (cur > col && array[cur] < array[cur - step]) {
Integer tmp = array[cur];
array[cur] = array[cur-step];
array[cur-step] = tmp;
cur -= step;
}
}
}
}
private List<Integer> shellStepSequence() {
List<Integer> stepSequence = new ArrayList<>();
int step = array.length;
while ((step >>= 1) > 0) {
stepSequence.add(step);
}
return stepSequence;
}
//目前已知的最好的步长序列，最坏情况时间复杂度是 O(n4/3) ，1986年由Robert Sedgewick提出
private List<Integer> sedgewickStepSequence() {
List<Integer> stepSequence = new LinkedList<>();
int k = 0, step = 0;
while (true) {
if (k % 2 == 0) {
int pow = (int) Math.pow(2, k >> 1);
step = 1 + 9 * (pow * pow - pow);
} else {
int pow1 = (int) Math.pow(2, (k - 1) >> 1);
int pow2 = (int) Math.pow(2, (k + 1) >> 1);
step = 1 + 8 * pow1 * pow2 - 6 * pow2;
}
if (step >= array.length) break;
stepSequence.add(0, step);
k++;
}
return stepSequence;
}
public static void main(String[] args) {
Integer[] array = {7,89,45,6,123,3,12,1};
Integers.println(array);
new QuickSort(array).sort();
Integers.println(array);
}
}
总结:
最好情况是步长序列只有1，且序列几乎有序，时间复杂度为 O(n)
空间复杂度为O(1)，属于不稳定排序
8. 计数排序
冒泡、选择、插入、归并、快速、希尔、堆排序，都是基于比较的排序, 平均时间复杂度目前最低是O(nlogn)
计数排序、桶排序、基数排序, 都不是基于比较的排序, 它们是典型的用空间换时间, 在某些时候,平均时间复杂度可以比O(nlogn)更低
思路:
将创建一个数组, 将待排序数组中的元素出现的次数全部记录在该数组中, 也就是在该数组中, 数组的索引相当于待排序数组中的元素值; 那么通过遍历该数组将该数组的索引映射到待排序数组中即可
public void sort0() {
// 找出最大值
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
} // O(n)
// 开辟内存空间，存储每个整数出现的次数
int[] counts = new int[1 + max];
// 统计每个整数出现的次数
for (int i = 0; i < array.length; i++) {
counts[array[i]]++;
} // O(n)
// 根据整数的出现次数，对整数进行排序
int index = 0;
for (int i = 0; i < counts.length; i++) {
while (counts[i]-- > 0) {
array[index++] = i;
}
} // O(n)
}
出现的问题:
1. 无法对负整数进行排序
2. 极其浪费内存空间
3. 是个不稳定的排序
优化思路:
流程演示:
@Override
protected void sort() {
// 找出最值
int max = array[0];
int min = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
if (array[i] < min) {
min = array[i];
}
}
// 开辟内存空间，存储次数
int[] counts = new int[max - min + 1];
// 统计每个整数出现的次数
for (int i = 0; i < array.length; i++) {
counts[array[i] - min]++;
}
// 累加次数
for (int i = 1; i < counts.length; i++) {
counts[i] += counts[i - 1];
}
// 从后往前遍历元素，将它放到有序数组中的合适位置
int[] newArray = new int[array.length];
for (int i = array.length - 1; i >= 0; i--) {
newArray[--counts[array[i] - min]] = array[i];
}
// 将有序数组赋值到array
for (int i = 0; i < newArray.length; i++) {
array[i] = newArray[i];
}
}
总结:
最好、最坏、平均时间复杂度: O(n + k)
空间复杂度: O(n + k)
稳定排序
9. 基数排序
思路:
基数排序非常适合用于整数排序(尤其是非负整数), 执行流程：依次对个位数、十位数、百位数、千位数、万位数...进行排序(从低位到高位,如果使用从高到低位排序, 那么低位排序会破坏高位排好序的数据) 注意: 个位数、十位数、百位数的取值范围都是固定的 0 ~ 9，可以使用计数排序对它们进行排序
public void sort() {
// 找出最大值
int max = array[0];
for (int i = 1; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
}
// 个位数: array[i] / 1 % 10 = 3
// 十位数：array[i] / 10 % 10 = 9
// 百位数：array[i] / 100 % 10 = 5
// 千位数：array[i] / 1000 % 10 = ...
for (int divider = 1; divider <= max; divider *= 10) {
countingSort(divider);
}
}
public void countingSort(int divider) {
// 开辟内存空间，存储次数
int[] counts = new int[10];
// 统计每个整数出现的次数
for (int i = 0; i < array.length; i++) {
counts[array[i] / divider % 10]++;
}
// 累加次数(用于确认当前基数需要排列在数组的位置)
for (int i = 1; i < counts.length; i++) {
counts[i] += counts[i - 1];
}
// 从后往前遍历元素，将它放到有序数组中的合适位置
int[] newArray = new int[array.length];
for (int i = array.length - 1; i >= 0; i--) {
//将元素放到根据排序基数在计数排序中确认的新数组中的位置
newArray[--counts[array[i] / divider % 10]] = array[i];
}
// 将有序数组赋值到array
for (int i = 0; i < newArray.length; i++) {
array[i] = newArray[i];
}
}
另一种思路:
创建一个二维数组, 每一列的大小为待排序数组的长度, 横向为0-9, 存储当前排序所用位的数字; 每一轮排序后, 扫描该二维数组, 即可获取根据某一位排序好的数字
10. 桶排序
思路:
1. 创建一定数量的桶(比如用数组、链表作为桶)
2. 按照一定的规则(不同类型的数据, 规则不同), 将序列中的元素均匀分配到对应的桶
3. 分别对每个桶进行单独排序
4. 将所有非空桶的元素合并成有序序列
元素在桶中的索引 = 元素值 * 元素数量
流程:
步骤(1)
步骤(2)(3)
步骤(4)
实现:
总结:
临渊羡鱼, 不如退而结网。加油!