| Introduction | The so-called sorting is to arrange the data elements in order according to the increasing or decreasing order of the sorting code, so that a set of randomly arranged elements becomes a set of linearly ordered elements according to their sorting code. This article will introduce the basic ideas and implementation of the eight most classic and commonly used internal sorting algorithms, including insertion sort (direct insertion sort, Hill sort), selection sort (direct selection sort, heap sort), exchange sort (bubble sort, quick sort) Sorting), merge sort, assignment sort (radix sort), and give the time complexity, space complexity and stability of various algorithms. |
If readers need the complete code related to this blog post, please go to my Github to get it yourself. The project name is DataStructure (the specific algorithm is implemented in the cn.tju.edu.rico.sort package), and the project link address is: https:/ /github.com/githubofrico/DataStructure.
Overview of sorting algorithmsThe so-called sorting is to arrange the data elements in order according to the increasing or decreasing order of the sorting code, so that a set of arbitrarily arranged elements becomes a set of linearly ordered elements according to their sorting code. This article will introduce the eight most classic and commonly used internal sorting algorithms, including insertion sort (direct insertion sort, Hill sort), selection sort (direct selection sort, heap sort), exchange sort (bubble sort, quick sort), and merge sort. , distribution sort (radix sort). In fact, whether it is a basic sorting method (direct insertion sort, direct selection sort, bubble sort) or an efficient sorting method (quick sort, heap sort, merge sort), etc., they all have their own strengths and specific usage scenarios. . Therefore, in practical applications, we must make the most appropriate choice based on the characteristics of the actual task and the characteristics of various sorting algorithms. Generally, the indicators we use to measure an algorithm include:
In this article, the author will focus on the ideas and implementation of the above eight sorting algorithms, and analyze and classify each algorithm according to the above indicators in order to further become familiar with their respective application scenarios.
2. Insertion sortThe basic idea of insertion sort: In each step, an element to be sorted is inserted into a group of previously sorted elements according to its sorting code size, until all elements are until inserted. Here, we introduce three specific insertion sort algorithms: direct insertion sort, Hill sort and half-way insertion sort.
1. Direct insertion sortThe idea of direct insertion sorting: When inserting the i-th (i>=1) element, the previous V[0],...,V[i-1] Wait for i-1 elements to be sorted. At this time, the i-th element is compared with the previous i-1 elements V[i-1],...,V[0] in sequence, and V[i] is inserted when the insertion position is found. At the same time, the elements at the original position are sequentially inserted backwards. shift. Here, the search at the insertion position is a sequential search. Direct insertion sort is a stable sorting algorithm, its implementation is as follows:
/**
* Title: 插入排序中的直接插入排序，依赖于初始序列
* Description: 在有序序列中不断插入新的记录以达到扩大有序区到整个数组的目的
* 时间复杂度：最好情形O(n)，平均情形O(n^2)，最差情形O(n^2)
* 空间复杂度：O(1)
* 稳 定 性：稳定
* 内部排序(在排序过程中数据元素完全在内存)
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class StraightInsertionSort {
public static int[] insertSort(int[] target){
if(target != null && target.length != 1){ // 待排序数组不为空且长度大于1
for (int i = 1; i 0; j--) { // 向有序序列中插入新的元素
if(target[j]
<span style="color: #1e1e1e; letter-spacing: 2px; border-left: #FF3030 3px solid; border-right: #FF3030 3px solid; padding-left: 8px; padding-right: 8px; font-size: 12pt;"><strong>2. Hill sorting</strong></span>
<p><span style="color: red;"><strong>The idea of Hill sorting: </strong></span> Assume that the sequence to be sorted has a total of n elements. First, take an integer gap<n as the interval and divide all elements into gaps with an of gap. subsequences perform direct insertion sorting on each subsequence. then reduce gap repeat above operation until shrinks to at this time are in same sequence ordered. because beginning is large subsequence has fewer speed faster later stage becomes smaller more but most basically ordered so still relatively slow. quick. generally taken hill unstable method its implementation follows:>
<pre class="brush:php;toolbar:false">/**
* Title: 插入排序中的希尔排序，依赖于初始序列
* Description: 分别对间隔为gap的gap个子序列进行直接插入排序，不断缩小gap,直至为 1
*
* 刚开始时，gap较大，每个子序列元素较少，排序速度较快；
* 待到排序后期，gap变小，每个子序列元素较多，但大部分元素基本有序，所以排序速度仍较快。
*
* 时间复杂度：O(n) ~ O(n^2)
* 空间复杂度：O(1)
* 稳 定 性：不稳定
* 内部排序(在排序过程中数据元素完全在内存)
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class ShellSort {
public static int[] shellSort(int[] target){
if(target != null && target.length != 1){
int gap = target.length; // gap个大小为gap的子序列
do{
gap = gap/3 + 1; // 不断缩小gap直至为1
for (int i = 0 + gap; i = 0 && target[j] > temp); // 向前比较的终止条件
target[j + gap] = temp; // 将待插入值插入合适的位置
}
}
}while(gap > 1);
}
return target;
}
}The idea of half insertion sort: When inserting the i-th (i>=1) element, the previous V[0],...,V[i-1] Wait for i-1 elements to be sorted. At this time, search in half for the insertion position of the i-th element in the previous i-1 elements V[i-1],...,V[0], and then directly insert V[i], while the elements at the original position are moved to Move later. Different from direct insertion sort, half insertion sort significantly reduces the number of comparisons between keywords than direct insertion sort, but the number of moves does not change. Therefore, the time complexity of half insertion sort and insertion sort is the same, O(N^2), but it reduces the number of comparisons, so the algorithm is still better than direct insertion sort. Half-way insertion sort is a stable sorting algorithm, and its implementation is as follows:
/**
* Title: 插入排序中的折半插入排序，依赖于初始序列
* Description: 折半搜索出插入位置，并直接插入;与直接插入搜索的区别是，后者的搜索要快于顺序搜索
* 时间复杂度：折半插入排序比直接插入排序明显减少了关键字之间的比较次数，但是移动次数是没有改变。所以，
* 折半插入排序和插入排序的时间复杂度相同都是O（N^2），在减少了比较次数方面它确实相当优秀，所以该算法仍然比直接插入排序好。
* 空间复杂度：O(1)
* 稳 定 性：稳定
* 内部排序(在排序过程中数据元素完全在内存)
* @author rico
* @created 2017年5月25日 下午12:03:23
*/
public class BinaryInsertSort {
public static int[] binaryInsertSort(int[] target) {
if (target != null && target.length > 1) {
for (int i = 1; i temp){
right = mid - 1; // 缩小插入区间
}else{ // 待插入值与有序序列中的target[mid]相等，保证稳定性的处理
left = left + 1;
}
}
// left及其后面的数据顺序向后移动，并在left位置插入
for (int j = i; j > left; j--) {
target[j] = target[j-1];
}
target[left] = temp;
}
}
}
return target;
}
}选择排序的基本思想：每一趟 (例如第i趟，i = 0,1,…)在后面第n-i个待排序元素中选出最小元素作为有序序列的第i个元素，直到第n-1趟结束后，所有元素有序。在这里，我们介绍两种具体的选择排序算法：直接选择排序与堆排序。
1、直接选择排序直接选择排序的思想：第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R1~R[n-1]中选取最小值，与R1交换，….，第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，…..，第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。直接选择排序是一种不稳定的排序算法，其实现如下：
/**
* Title: 选择排序中的直接选择排序，依赖于初始序列
* Description: 每一趟 (例如第i趟，i = 0,1,...)在后面第n-i个待排序元素中选出最小元素作为有序序列的第i个元素
* 时间复杂度：最好情形O(n^2)，平均情形O(n^2)，最差情形O(n^2)
* 空间复杂度：O(1)
* 稳 定 性：不稳定
* 内部排序(在排序过程中数据元素完全在内存)
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class StraightSelectSort {
public static int[] selectSort(int[] target){
if(target != null && target.length != 1){
for (int i = 0; i target[j]){
min_index = j;
}
}
if(target[min_index] != target[i]){ // 导致不稳定的因素：交换
int min = target[min_index];
target[min_index] = target[i];
target[i] = min;
}
}
}
return target;
}
}堆排序的核心是堆调整算法。首先根据初始输入数据，利用堆调整算法shiftDown()形成初始堆；然后，将堆顶元素与堆尾元素交换，缩小堆的范围并重新调整为堆，如此往复。堆排序是一种不稳定的排序算法，其实现如下：
/**
* Title: 堆排序(选择排序)，升序排序(最大堆)，依赖于初始序列
* Description: 现将给定序列调整为最大堆，然后每次将堆顶元素与堆尾元素交换并缩小堆的范围，直到将堆缩小至1
* 时间复杂度：O(nlgn)
* 空间复杂度：O(1)
* 稳 定 性：不稳定
* 内部排序(在排序过程中数据元素完全在内存)
* @author rico
* @created 2017年5月25日 上午9:48:06
*/
public class HeapSort {
public static int[] heapSort(int[] target) {
if (target != null && target.length > 1) {
// 调整为最大堆
int pos = (target.length - 2) / 2;
while (pos >= 0) {
shiftDown(target, pos, target.length - 1);
pos--;
}
// 堆排序
for (int i = target.length-1; i > 0; i--) {
int temp = target[i];
target[i] = target[0];
target[0] = temp;
shiftDown(target, 0, i-1);
}
return target;
}
return target;
}
/**
* @description 自上而下调整为最大堆
* @author rico
* @created 2017年5月25日 上午9:45:40
* @param target
* @param start
* @param end
*/
private static void shiftDown(int[] target, int start, int end) {
int i = start;
int j = 2 * start + 1;
int temp = target[i];
while (j target[j]) { //找出较大子女
j = j + 1;
}
if (target[j]
<strong>四. 交换排序</strong>
<p><span style="color: red;"><strong>交换排序的基本思想：</strong></span>根据序列中两个元素的比较结果来对换这两个记录在序列中的位置，也就是说，将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。</p>
<span style="color: #1e1e1e; letter-spacing: 2px; border-left: #FF3030 3px solid; border-right: #FF3030 3px solid; padding-left: 8px; padding-right: 8px; font-size: 12pt;"><strong>1、冒泡排序</strong></span>
<p><span style="color: red;"><strong>冒泡排序的思想：</strong></span>根据序列中两个元素的比较结果来对换这两个记录在序列中的位置，将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。因此，每一趟都将较小的元素移到前面，较大的元素自然就逐渐沉到最后面了，也就是说，最大的元素最后才能确定，这就是冒泡。冒泡排序是一种稳定的排序算法，其实现如下：</p>
<pre class="brush:php;toolbar:false">/**
* Title: 交换排序中的冒泡排序 ，一般情形下指的是优化后的冒泡排序，最多进行n-1次比较，依赖于初始序列
* Description:因为越大的元素会经由交换慢慢"浮"到数列的顶端(最后位置)，最大的数最后才确定下来，所以称为冒泡排序
* 时间复杂度：最好情形O(n)，平均情形O(n^2)，最差情形O(n^2)
* 空间复杂度：O(1)
* 稳 定 性：稳定
* 内部排序(在排序过程中数据元素完全在内存)
*
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class BubbleSort {
/**
* @description 朴素冒泡排序(共进行n-1次比较)
* @author rico
*/
public static int[] bubbleSort(int[] target) {
int n = target.length;
if (target != null && n != 1) {
// 最多需要进行n-1躺，每一趟将比较小的元素移到前面，比较大的元素自然就逐渐沉到最后面了，这就是冒泡
for (int i = 0; i i; j--) {
if(target[j] i; j--) {
if(target[j]
<span style="color: #1e1e1e; letter-spacing: 2px; border-left: #FF3030 3px solid; border-right: #FF3030 3px solid; padding-left: 8px; padding-right: 8px; font-size: 12pt;"><strong>2、快速排序</strong></span>
<p><span style="color: red;"><strong>快速排序的思想：</strong></span>通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小(划分过程)，然后再按此方法对这两部分数据分别进行快速排序(快速排序过程)，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序是一种不稳定的排序算法。</p>
<pre class="brush:php;toolbar:false">/**
* Title: 交换排序中的快速排序，目前应用最为广泛的排序算法，是一个递归算法，依赖于初始序列
* Description:快速排序包括两个过程：划分 和 快排
* "划分"是指将原序列按基准元素划分两个子序列
* "快排"是指分别对子序列进行快排
*
* 就平均计算时间而言，快速排序是所有内部排序方法中最好的一个
*
* 对大规模数据排序时，快排是快的；对小规模数据排序时，快排是慢的，甚至慢于简单选择排序等简单排序方法
*
* 快速排序依赖于原始序列，因此其时间复杂度从O(nlgn)到O(n^2)不等
* 时间复杂度：最好情形O(nlgn)，平均情形O(nlgn)，最差情形O(n^2)
*
* 递归所消耗的栈空间
* 空间复杂度：O(lgn)
*
* 可选任一元素作为基准元素
* 稳 定 性：不稳定
*
*
* 内部排序(在排序过程中数据元素完全在内存)
*
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class QuickSort {
/**
* @description 快排算法(递归算法)：在递去过程中就把问题解决了
* @author rico
* @created 2017年5月20日 下午5:12:06
* @param target
* @param left
* @param right
* @return
*/
public static int[] quickSort(int[] target, int left, int right) {
if(right > left){ // 递归终止条件
int base_index = partition(target,left, right); // 原序列划分后基准元素的位置
quickSort(target, left, base_index-1); // 对第一个子序列快速排序，不包含基准元素！
quickSort(target, base_index+1, right); // 对第二个子序列快速排序，不包含基准元素！
return target;
}
return target;
}
/**
* @description 序列划分，以第一个元素为基准元素
* @author rico
* @created 2017年5月20日 下午5:10:54
* @param target 序列
* @param left 序列左端
* @param right 序列右端
* @return
*/
public static int partition(int[] target, int left, int right){
int base = target[left]; // 基准元素的值
int base_index = left; // 基准元素最终应该在的位置
for (int i = left+1; i
<strong>五. 归并排序</strong>
<p><span style="color: red;"><strong>归并排序包含两个过程：”归”和”并”。</strong></span>其中，”归”是指将原序列分成半子序列，分别对子序列进行递归排序；”并”是指将排好序的各子序列合并成原序列。归并排序算法是一个典型的递归算法，因此也是概念上最为简单的排序算法。与快速排序算法相比，归并排序算法不依赖于初始序列，并且是一种稳定的排序算法，但需要与原序列一样大小的辅助存储空间。</p>
<pre class="brush:php;toolbar:false">/**
* Title: 归并排序 ，概念上最为简单的排序算法，是一个递归算法，不依赖于初始序列
* Description:归并排序包括两个过程：归 和 并
* "归"是指将原序列分成半子序列，分别对子序列进行递归排序
* "并"是指将排好序的各子序列合并成原序列
*
* 归并排序的主要问题是：需要一个与原待排序数组一样大的辅助数组空间
*
* 归并排序不依赖于原始序列，因此其最好情形、平均情形和最差情形时间复杂度都一样
* 时间复杂度：最好情形O(n)，平均情形O(n^2)，最差情形O(n^2)
* 空间复杂度：O(n)
* 稳 定 性：稳定
* 内部排序(在排序过程中数据元素完全在内存)
*
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class MergeSort {
/**
* @description 归并排序算法(递归算法)：递去分解，归来合并
* @author rico
* @created 2017年5月20日 下午4:04:52
* @param target 待排序序列
* @param left 待排序序列起始位置
* @param right 待排序序列终止位置
* @return
*/
public static int[] mergeSort(int[] target, int left, int right) {
if(right > left){ // 递归终止条件
int mid = (left + right)/2;
mergeSort(target, left, mid); // 归并排序第一个子序列
mergeSort(target, mid+1, right); // 归并排序第二个子序列
return merge(target,left,mid,right); // 合并子序列成原序列
}
return target;
}
/**
* @description 两路归并算法
* @author rico
* @created 2017年5月20日 下午3:59:16
* @param target 用于存储归并结果
* @param left 第一个有序表的第一个元素所在位置
* @param mid 第一个有序表的最后一个元素所在位置
* @param right 第二个有序表的最后一个元素所在位置
* @return
*/
public static int[] merge(int[] target, int left, int mid, int right){
// 需要一个与原待排序数组一样大的辅助数组空间
int[] temp = Arrays.copyOf(target, target.length);
// s1,s2是检查指针，index 是存放指针
int s1 = left;
int s2 = mid + 1;
int index = left;
// 两个表都未检查完，两两比较
while(s1
<p>Ps : 归并排序和快速排序都是典型的递归算法，因此它们比较容易理解和实现。关于递归思想和内涵深度剖析，请见博文《算法设计方法：递归的内涵与经典应用》。</p>
<strong>六. 分配排序(基数排序)</strong>
<p><span style="color: red;"><strong>分配排序的基本思想</strong></span>：用空间换时间。在整个排序过程中，无须比较关键字，而是通过用额外的空间来”分配”和”收集”来实现排序，它们的时间复杂度可达到线性阶：O(n)。其中，基数排序包括两个过程：首先，将目标序列各元素分配到各个桶中(分配过程)；然后，将各个桶中的元素按先进先出的顺序再放回去(收集过程)，如此往复，一共需要进行d趟，d为元素的位数。</p>
<pre class="brush:php;toolbar:false">/**
* Title: 分配排序中的基数排序，不依赖于初始序列
* Description: 不是在对元素进行比较的基础上进行排序，而是采用 "分配 + 收集" 的办法
*
* 首先，将目标序列各元素分配到各个桶中；
* 其次，将各个桶中的元素按先进先出的顺序再放回去
* 如此往复...
*
* 时间复杂度：O(d*(r+n))或者 O(dn),d 的大小一般会受到 n的影响
* 空间复杂度：O(rd + n)或者 O(n)
* 稳 定 性：稳定
* 内部排序(在排序过程中数据元素完全在内存)
* @author rico
* @created 2017年5月20日 上午10:40:00
*/
public class RadixSort {
/**
* @description 分配 + 收集
* @author rico
* @created 2017年5月21日 下午9:25:52
* @param target 待排序数组
* @param r 基数
* @param d 元素的位数
* @param n 待排序元素个数
* @return
*/
public static int[] radixSort(int[] target, int r, int d, int n){
if (target != null && target.length != 1 ) {
int[][] bucket = new int[r][n]; // 一共有基数r个桶，每个桶最多放n个元素
int digit; // 获取元素对应位上的数字，即装入那个桶
int divisor = 1; // 定义每一轮的除数，1, 10, 100, ...
int[] count = new int[r]; // 统计每个桶中实际存放元素的个数
for (int i = 0; i
<strong>七. 总结</strong>
<p><img src="https://img.php.cn/upload/article/000/000/164/170426878460228.jpg" alt="Explanation and comparison of eight sorting algorithms"></p>
<span style="color: #1e1e1e; letter-spacing: 2px; border-left: #FF3030 3px solid; border-right: #FF3030 3px solid; padding-left: 8px; padding-right: 8px; font-size: 12pt;"><strong>1、直接插入排序 Vs. 折半插入排序 Vs. 希尔排序</strong></span>
<p>这三种排序方法都属于插入排序的范畴。与直接插入排序的顺序搜索插入位置相比，折半插入排序通过折半搜索的方法搜索插入位置，因此，在搜索插入位置方面，折半插入排序要快于直接插入排序。实际上，折半插入排序比直接插入排序只是减少了关键字之间的比较次数，但是移动次数是没有改变。所以，折半插入排序和插入排序的时间复杂度相同都是O（n^2），但减少了比较次数，所以该算法要比直接插入排序好一点。希尔排序可以看作是对直接插入排序的一种优化，它将全部元素分为间隔为gap的gap个子序列并对每一个子序列进行直接插入排序，同时不断缩小间隔gap，直至所有元素位于同一个序列。使用这种方式可以保证排序效率，因为刚开始时，gap较大，每个子序列元素较少，排序速度较快；待到排序后期，gap变小，每个子序列元素较多，但大部分元素基本有序，所以排序速度仍较快。因此，希尔排序比直接插入排序 、折半插入排序都要高效，但它不是稳定的。</p>
<span style="color: #1e1e1e; letter-spacing: 2px; border-left: #FF3030 3px solid; border-right: #FF3030 3px solid; padding-left: 8px; padding-right: 8px; font-size: 12pt;"><strong>2、直接选择排序 Vs. 堆排序</strong></span>
<p>这两种排序方法都属于插入选择排序的范畴，它们的核心思想都是每一趟都选择一个极值元素放在靠前/靠后位置，直到序列有序。与直接选择排序不同的是，堆排序不是“蛮力选择”，而是不断进行堆调整以取得每趟中的极值。因此，堆排序比直接选择排序要高效，不过它们都是不稳定的。</p>
<span style="color: #1e1e1e; letter-spacing: 2px; border-left: #FF3030 3px solid; border-right: #FF3030 3px solid; padding-left: 8px; padding-right: 8px; font-size: 12pt;"><strong>3、冒泡排序 Vs. 快速排序</strong></span>
<p>这两种排序方法都属于选择排序的范畴，它们的核心思想都是元素的交换，冒泡排序中每一趟相邻元素互相比较，并将较小的交换到前面(较大的自然沉到后面)位置，快速排序则是以基准点为基础，将比它小的元素和比它大的元素分别交换到它的两边。因此，快速排序比冒泡排序要高效，但它不是稳定的。</p>
<span style="color: #1e1e1e; letter-spacing: 2px; border-left: #FF3030 3px solid; border-right: #FF3030 3px solid; padding-left: 8px; padding-right: 8px; font-size: 12pt;"><strong>4、归并排序 Vs. 快速排序</strong></span>
<p>这两种排序方法都属于递归算法的范畴，因此，它们都比较容易让人理解和实现。与快速排序相比，归并排序不但是稳定的，还是与原始序列无关的(不依赖于原始序列的顺序，时间复杂度总是O(nlgn))，但是需要与原始序列一样大小的空间；而快速排序则一般情况下都要比其他高效排序算法（包括归并排序）快，而且空间复杂度只为O(1)。另外，我们从算法实现中可以看出这两种递归算法有以下区别和联系：</p>
直接插入排序、直接选择排序和冒泡排序是基本的排序方法，它们平均情况下的时间复杂度都是O(n^2)，实现也比较简单，它们对规模较小的元素序列很有效。
快速排序、堆排序和归并排序是高效的排序方法，它们平均情况下的时间复杂度都是O(nlgn)，其中快速排序是最通用的高效排序算法，但其是不稳定的；归并排序是上述几种排序算法中唯一与初始序列无关的，而且时间复杂度总是O(nlgn)，但其空间复杂度是O(n)，是一种稳定的排序算法；堆排序的时间复杂度总是O(nlgn)，空间复杂度是O(1)，也是不稳定的。它们对规模较大的元素序列很有效。
The efficiency of Hill sorting is between the basic sorting method and the efficient sorting method. It is an unstable sorting algorithm. They each have their own strengths and specific usage scenarios. Although radix sort has linearly increasing time complexity, its actual cost is not much smaller than quick sort, and its application is relatively less widespread.
Therefore, in practical applications, we must make the most appropriate choice based on the characteristics of the actual task and the characteristics of various sorting algorithms.
8. MoreMerge sort and quick sort are both typical recursive algorithms, so they are relatively easy to understand and implement. For an in-depth analysis of recursive ideas and connotations, please see the blog post "Algorithm Design Methods: The Connotation and Classic Applications of Recursion".
The above is the detailed content of Explanation and comparison of eight sorting algorithms. For more information, please follow other related articles on the PHP Chinese website!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
