本文主要是介绍排序算法见解（1），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.冒泡排序
1.1基本思想：
1.2基本思路：
（1）比较相邻的元素：如果第一个比第二个大，就交换它们两个。
（2）对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
（3）针对所有的元素重复以上的步骤，除了最后一个。
（4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
1.3图解过程：
动图演示：
1.4代码实现：
每一趟排序结束后把当前遍历的最大值放在最后位置
//冒泡排序
void Bubble_sort(int* arr, int n)
{for (int i = 0; i < n - 1; i++){for (int j = 0; j < n - i - 1; j++){if (arr[j] > arr[j + 1]){int t = arr[j];arr[j] = arr[j + 1];arr[j + 1] = t;}}}
}2.选择排序
2.1基本思想：
选择排序是在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。重复上一步，直到所有元素均排序完毕。
2.2基本思路：
（1）初始状态：假设有一个数组arr，长度为n。未排序序列为arr[0....n-1]，已排序序列为空。
（2）第一轮选择：从arr[0]到arr[n-1]中选择最小元素，假设是arr[i]，与arr[0]交换位置。此时，arr[0]到arr[0]为已排序序列，arr[1]到arr[n-1]为未排序序列。
（3）第二轮选择：在未排序序列arr[1..n-1]中继续寻找最小元素，假设是arr[j]，与arr[1]交换位置。此时，arr[0]到arr[1]为已排序序列，arr[2]到arr[n-1]为未排序序列。
（4）重复进行：每一轮都从剩余的未排序序列中选出最小元素，放到已排序序列的末尾，直到所有元素都被排序。
2.3图解过程：
动图展示：
2.4代码实现：
每趟找到最小值，把最小值放在本次寻找的范围第一个位置，这里为了提高效率，选择从两头找，分别找最大值和最小值
//选择排序
void Select_Sort(int* arr, int n)
{int begin = 0;int end = n - 1;while (begin < end){int minx = begin;int maxx = begin;for (int i = begin + 1; i < end; i++){if (arr[i] < arr[minx]){minx = i;}if (arr[i] > arr[maxx]){maxx = i;}}Swap(&arr[minx], &arr[begin]);if (maxx == begin)//这是最大值在第一个位置时候maxx = minx;Swap(&arr[maxx], &arr[end]);end--;begin++;}
}3.插入排序
3.1基本思想：
插入排序是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。在从后向前扫描过程中，找到排序位置后，需要将已排序元素逐步向后挪位，为最新元素提供插入空间。
3.2基本思路：
（1）初始状态：假设第一个元素是已排序的（或者认为它是一个只有一个元素的已排序序列）。
（2）从第二个元素开始遍历：取出下一个元素（记为当前元素），在已经排序的序列中从后向前扫描。
（3）寻找插入位置：如果当前元素小于扫描到的元素，则将该元素移到下一位置。
（4）重复步骤3，直到找到已排序的元素小于或等于当前元素的位置。
（5）插入元素：将当前元素插入到该位置后（即已排序序列的该位置后移，为新元素腾出空间）。
（6）重复步骤2~5：对序列中的下一个元素重复以上过程，直到整个序列排序完成。
3.3图解过程：
动图演示：
3.4代码实现：
前 i 个数当成有序的数组，把第 i+1 个数按照大小插入到数组中
//插入排序
void Insertion_Sort(int* arr, int n)
{for (int i = 0; i < n - 1; i++){//进行单趟排序(首先设置前 end 个数为有序的)int end = i;int temp = arr[end + 1];while (end >= 0){if (temp < arr[end]){arr[end + 1] = arr[end];arr[end] = temp;end--;}else{break;}}arr[end + 1] = temp;}
}4.希尔排序
4.1基本思想：
希尔排序是一种基于插入排序的算法，其基本思路是通过设置不同的间隔序列（也称为增量序列）来将待排序的序列分割成若干个子序列，然后分别对这些子序列进行插入排序。随着间隔的逐渐减小，每个子序列包含的元素越来越多，直至间隔为1时，整个序列被视为一个子序列进行最后一次插入排序，从而完成整个排序过程。
4.2基本思路：
（1）选择初始间隔：通常选择序列长度的一半作为初始间隔（gap），即gap = length / 2。这个间隔用于将序列分割成若干个子序列。
（2）分组并排序：根据当前的间隔，将序列中的元素分组。具体来说，将间隔为gap的元素视为同一组，并对这些组内的元素进行插入排序。由于间隔的存在，这种插入排序并不是传统的相邻元素之间的比较和移动，而是间隔为gap的元素之间的比较和移动。
（3）缩小间隔：完成当前间隔下的分组和排序后，将间隔减半（gap = gap / 2），然后重复步骤2，继续对新的子序列进行插入排序。这个过程会一直重复，直到间隔为1。
（4）最后一次插入排序：当间隔减至1时，整个序列被视为一个子序列，此时进行一次普通的插入排序，完成整个排序过程。
4.3图解过程：
动图演示：
4.4代码实现：
分成间隔gap进行插入排序
//希尔排序 O(N^1.3)
void Shell_Sort(int* arr, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int temp = arr[end + gap];while (end >= 0){if (temp < arr[end]){arr[end + gap] = arr[end];arr[end] = temp;end -= gap;}else{break;}}arr[end + gap] = temp;}}
}5.堆排序
5.1基本思想：
堆排序是一种基于比较的排序算法，它利用堆这种数据结构所设计。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。
5.2基本思路：
（1）构建堆：从最后一个非叶子节点开始，向前遍历每个节点，对每个节点进行下沉操作，确保每个节点都满足堆的性质。对于大顶堆，下沉操作是确保节点的值大于其子节点的值；对于小顶堆，则是确保节点的值小于其子节点的值。
（2）排序：将堆顶元素（即当前最大值或最小值）与堆数组的末尾元素交换，然后减少堆的大小（即不考虑已经排序好的末尾元素），并重新对新的堆顶元素执行下沉操作，以保持堆的性质。重复这个过程，直到堆的大小为1，此时数组就完全有序了。
5.3图解过程：
动态演示：
5.4代码实现：
先建立小堆进行预排序，再通过向下调整建大堆
//向上调整
void AdjustHeapUp(type* arr, int child)
{int parent = (child - 1) / 2;while (child > 0){if (arr[parent] > arr[child]){Sweap(&arr[parent], &arr[child]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//向下调整
void AdjustHeapDown(type*arr,int n,int parent)
{int child = 2 * parent + 1;//找最小的那一个while (child < n){if (child + 1 < n && arr[child] > arr[child + 1]){child++;}if (arr[child] < arr[parent]){Sweap(&arr[child], &arr[parent]);parent = child;child = 2 * parent + 1;}else{break;}printf("\n");}
}void HeapSort(int* a, int n)
{for (int i = 1; i < n; i++){AdjustHeapUp(a, i);}printf("\n");int k = n - 1;while (k > 0){Sweap(&a[0], &a[k]);AdjustHeapDown(a, k, 0);k--;}
}
这篇关于排序算法见解（1）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
