社区微信群开通啦，扫一扫抢先加入社区官方微信群
社区微信群
社区微信群开通啦，扫一扫抢先加入社区官方微信群
社区微信群
什么是排序？将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程就叫做排序。本篇文章将介绍十种经典的排序算法，在此之前，我们先介绍几个名词的含义。
下面我们开始介绍各大排序算法的原理与代码实现，其中代码实现采用 Java 的形式。
所谓冒泡，就是在序列中对两个相邻的元素进行比较，较大的数下沉，而较小的数冒起来。
//冒泡排序算法实现
public static int[] bubbleSort(int[] array) {
if (array.length == 0) {
return array;
}
for (int i = 0; i < array.length; i++) {
for (int j = 0; j < array.length - 1 - i; j++) {
if (array[j + 1] < array[j]) {
int temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
}
}
return array;
}
从未排序序列中找出最小值并将其移至已排序序列的末尾，然后依次类推即可。
//选择排序算法实现
public static int[] selectionSort(int[] array) {
if (array.length == 0) {
return array;
}
for (int i = 0; i < array.length; i++) {
int minIndex = i;
for (int j = i; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
int temp = array[minIndex];
array[minIndex] = array[i];
array[i] = temp;
}
return array;
}
我们假设，在要排序的序列中，前 n - 1 个元素已经排序完毕，现在我们将第 n 个元素插入到前面的有序序列中，使前 n 个元素有序，依次循环即可。
//插入排序算法实现
public static int[] insertionSort(int[] array) {
if (array.length == 0) {
return array;
}
int current;
for (int i = 0; i < array.length - 1; i++) {
current = array[i + 1];
int preIndex = i;
while (preIndex >= 0 && current < array[preIndex]) {
array[preIndex + 1] = array[preIndex];
preIndex--;
}
array[preIndex + 1] = current;
}
return array;
}
希尔排序就是一种特殊的插入排序，它首先会选择一个增量序列 t1，t2，…，tk（ti > tj，tk = 1），然后按增量序列个数 k，对序列进行 k 趟排序。每趟排序，根据对应的增量 ti，将待排序列分割成若干子序列，分别对各子序列进行插入排序。仅增量因子为1时会将整个序列作为一个表来处理。
希尔排序的核心在于间隔序列的设定，既可以提前设定好间隔序列，也可以动态地定义间隔序列。
//希尔排序算法实现
public static int[] ShellSort(int[] array) {
int len = array.length;
int temp, gap = len / 2;
while (gap > 0) {
for (int i = gap; i < len; i++) {
temp = array[i];
int preIndex = i - gap;
while (preIndex >= 0 && array[preIndex] > temp) {
array[preIndex + gap] = array[preIndex];
preIndex -= gap;
}
array[preIndex + gap] = temp;
}
gap /= 2;
}
return array;
}
归并排序是分治法的典型应用，首先将一个长度为 n 的序列分成两个长度为 n / 2 的序列，分别对其进行归并排序，最后将两个已排序的序列合并为一个有序序列。
//归并排序算法实现
public static int[] MergeSort(int[] array) {
if (array.length < 2) {
return array;
}
int mid = array.length / 2;
int[] left = Arrays.copyOfRange(array, 0, mid);
int[] right = Arrays.copyOfRange(array, mid, array.length);
return merge(MergeSort(left), MergeSort(right));
}
//将两段已排序的序列结合成一段已排序的序列
public static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
for (int index = 0, i = 0, j = 0; index < result.length; index++) {
if (i >= left.length) {
result[index] = right[j++];
}else if (j >= right.length) {
result[index] = left[i++];
}else if (left[i] > right[j]) {
result[index] = right[j++];
}else {
result[index] = left[i++];
}
}
return result;
}
快速排序运用了分治法的思想，首先选出基准元素，通过一趟排序将待排序列分隔成独立的两部分，其中一部分大于基准元素，一部分小于基准元素，然后对这两部分序列继续排序，最终可使整个序列有序。
//快速排序算法实现
private static void quickSort(int[] a,int low, int high) {
if(low < high){
int middle = getMiddle(a,low,high);
quickSort(a,0,middle-1);
quickSort(a,middle+1,high);
}
}
//将序列分成比基准元素大以及比基准元素小的两部分
//并得到基准元素的最终位置
public static int getMiddle(int[] a, int low, int high){
int key = a[low];//基准元素
while(low < high){
while(low < high && a[high] >= key){
high--;
}
a[low] = a[high];
while(low < high && a[low] <= key){
low++;
}
a[high] = a[low];
}
a[low] = key;
return low;
}
堆排序使用了堆这一数据结构。首先构建一个最大堆，然后将首位（也就是最大值）与末位进行交换，并重新调整最大堆，经过该操作后最大值已经到达未排序序列的末尾，不断重复该操作即可。
//堆排序算法实现
public static int[] heapSort(int[] array) {
int len = array.length;
if (len < 1) {
return array;
}
//构建最大堆
buildMaxHeap(array);
while (len > 0) {
//将堆首位（最大值）与末位交换
swap(array,0,len - 1);
len--;
//重新调整最大堆
adjustHeap(array,0,len);
}
return array;
}
//构建最大堆
public static void buildMaxHeap(int[] array) {
//从最后一个非叶子节点开始向上构造最大堆
for (int i = (array.length / 2 - 1); i >= 0; i--) {
adjustHeap(array,i,array.length);
}
}
//调整最大堆,使其满足最大堆的性质
public static void adjustHeap(int[] array,int i,int len) {
int maxIndex = i;
//如果有左子树，且左子树大于父节点，则将最大指针指向左子树
if (i * 2 < len && array[i * 2] > array[maxIndex]) {
maxIndex = i * 2;
}
//如果有右子树，且右子树大于父节点，则将最大指针指向右子树
if (i * 2 + 1 < len && array[i * 2 + 1] > array[maxIndex]) {
maxIndex = i * 2 + 1;
}
//如果父节点不是最大值，则将父节点与最大值交换，并且递归调整与父节点交换的位置。
if (maxIndex != i) {
swap(array,maxIndex,i);
adjustHeap(array,maxIndex,len);
}
}
//交换序列的两个元素
public static void swap(int[] array,int i,int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
统计序列中每个值为 i 的元素出现的次数，存入新数组的第 i 项，然后再反向填充目标数组即可。
计数排序的时间复杂度是线性的，而且其数据必须是有确定范围的整数。
//计数排序算法实现
public static int[] countingSort(int[] array) {
if (array.length == 0) {
return array;
}
int bias,min = array[0],max = array[0];
for (int i = 1;i < array.length;i++) {
if (array[i] > max) {
max = array[i];
}
if (array[i] < min) {
min = array[i];
}
}
bias = 0 - min;
int[] bucket = new int[max - min + 1];
Arrays.fill(bucket, 0);
for (int i = 0;i < array.length;i++) {
bucket[array[i] + bias]++;
}
int index = 0,i = 0;
while (index < array.length) {
if (bucket[i] != 0) {
array[index] = i - bias;
bucket[i]--;
index++;
}else {
i++;
}
}
return array;
}
桶排序是计数排序的扩展，计数排序中每个桶只存储相同元素，而桶排序每个桶存储一定范围的元素，通过映射函数，将待排序数组中的元素映射到各个对应的桶中，对每个桶中的元素进行排序，最后将非空桶中的元素逐个放入原序列中。
桶排序需要尽量保证元素分散均匀，否则当所有数据集中在同一个桶中时，桶排序失效。
//桶排序算法实现
public static int[] bucketSort(int[] array){
if (array.length == 0) {
return array;
}
int min = array[0],max = 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 bucketNum = (max - min) / array.length + 1;//桶的数量
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for(int i = 0; i < bucketNum; i++){
bucketArr.add(new ArrayList<Integer>());
}
for(int i = 0; i < array.length; i++){//将元素插入桶
int num = (array[i] - min) / (array.length);
bucketArr.get(num).add(array[i]);
}
for(int i = 0; i < bucketArr.size(); i++){//对每个桶进行排序
Collections.sort(bucketArr.get(i));
}
int index = 0;
for(int i = 0; i < bucketArr.size(); i++){
for(int j = 0; j < bucketArr.get(i).size(); j++){
array[index++] = bucketArr.get(i).get(j);
}
}
return array;
}
基数排序就是先低位排序，再收集；然后逐步向高位排序并收集，最终可得到有序的序列。
//基数排序算法实现
public static int[] radixSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
int max = array[0];
for (int i = 1;i < array.length;i++) {
max = Math.max(max, array[i]);
}
int maxDigit = 0;//最大数的位数
while (max != 0) {
max /= 10;
maxDigit++;
}
int mod = 10,div = 1;
ArrayList<ArrayList<Integer>> bucketList = new ArrayList<ArrayList<Integer>>();
for (int i = 0;i < 10;i++) {
bucketList.add(new ArrayList<Integer>());
}
for (int i = 0;i < maxDigit;i++,mod *= 10,div *= 10) {
for (int j = 0;j < array.length;j++) {
int num = (array[j] % mod) / div;
bucketList.get(num)
版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/Geffin/article/details/104226043
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。
如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！
