当前位置：首页 > news >正文

希尔排序和选择排序及计数排序的简单介绍

news 2025/7/13 14:28:06

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数gap，把待排序文件中所有数据分成几个组，所有距离为gap的数据分在同一组内，并对每一组内的数据进行排序。然后gap减减，重复上述分组和排序的工作。当到达gap=1时，所有数据在同一组内排好序（gap==1时就是上次讲的插入排序）。

希尔排序举例：

#include <stdio.h>
// 打印
void Printarry(int* arr, int n)
{assert(arr);for (int i = 0;i < n;i++){printf("%d ", arr[i]);}printf("\n");
}
// 希尔排序
// 时间复杂度 O（N^1.3-N^2)
// gap越大，前面大的数据可以越快排到后面，后面小的数可以越快拍到前面，gap越大，越不接近有序
// gap越小越接近有序，如果gap==1其实就是直接插入排序，就有序了
void ShellSort(int* arr, int n)
{assert(arr);int gap = n;// gap>1相当于预排序，让数组接近有序// gap==1就相当于直接插入排序，保证有序while (gap > 1){gap = gap / 3 + 1; // +1是保证了最后一次gap一定是1// 注意结束条件，防止造成越界访问（画图）for (int i = 0;i < n - gap;i++)  // 多趟并排{// 单趟排序int end = i;               // 当end==0时就是单趟排序，排间距为gap的那一趟int temp = arr[end + gap];  // 将新的排序数值存起来，方便每次比较大小while (end >= 0)   {if (temp < arr[end]){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = temp;  // 跳出循环后temp放到end+gap位置}// 打印每一个gap时的排序状态Printarry(arr, n);}}void TestShellSort() 
{int arr[] = { 3,1,4,2,8,4,9,6,0,7 };Printarry(arr, sizeof(arr) / sizeof(arr[0]));ShellSort(arr, sizeof(arr) / sizeof(arr[0]));Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}int main()
{TestShellSort();return 0;
}

选择排序

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置（末尾位置），直到全部待排序的数据元素排完。

直接选择排序:

在元素集合arr[i]--arr[n-1]中选择最大(小)的数据若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素。

举例：利用双指方法，begin指向首元素，end指向末尾元素，找到最大值时maxi和end位置数据互换，最小值mini位置和begin位置数据互换。

当begin和maxi重叠时，mini位置的数据和begin位置的数据互换后要将mini的值给到maxi，在将maxi位置的数据和end位置的数据互换。

#include <stdio.h>
// 打印
void Printarry(int* arr, int n)
{assert(arr);for (int i = 0;i < n;i++){printf("%d ", arr[i]);}printf("\n");
}
// 选择排序
// 空间复杂度为O（1）
// 时间复杂度为 O（N^2）,最好的情况是接近有序比较n次即可，最坏的是不完全有序接近无顺序
void SelectSort(int* arr, int n)
{assert(arr);int begin = 0;int end = n - 1;//int mini = 0;//int maxi = 0;while (begin < end){int mini = 0;int maxi = 0;maxi = mini = begin;// 在[begin，end]之间选出最大值和最小值for (int i = begin + 1;i <= end;++i){if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}Swap(&arr[begin], &arr[mini]);// 如果maxi与begin位置重叠的话要修正maxi的位置if (begin == maxi)maxi = mini;Swap(&arr[end], &arr[maxi]);--end;++begin;}
}void TestSelectSort()
{int arr[] = { 15,18,23,3,1,14,2,8,4,9,6,0,7 };SelectSort(arr, sizeof(arr) / sizeof(arr[0]));Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}
int main()
{TestShellSort();return 0;
}

计数排序

首先找到待排序数组的最大值和最小值，然后开辟一个空间temp数组，大小为最大值减去最小值加1；然后遍历数组，将数据出现的次数放到temp数组相对位置中；然后再遍历temp数组取出对应数据出现的次数，将该数据依次覆盖回原数组中。

注意：这个排序缺点就是浪费空间比如，待排序数组最小值为100，最大值为1000；那么要开辟0-1000个空间的数组，才能存放比如100出现10次，那么temp数组中下标100位置就存放10，这样就很浪费空间。我们在这里开辟900个空间的数组，将100出现的次数放到相对位置中，相对位置为：100-min。覆盖回原数组的时候再加上min即可。相对减少空间浪费。

举例子：

#include <stdio.h>
// 打印
void Printarry(int* arr, int n)
{assert(arr);for (int i = 0;i < n;i++){printf("%d ", arr[i]);}printf("\n");
}
// 计数排序
// 时间复杂度O(N+range)
// 空间复杂度O(range)
void CountSort(int* arr, int n)
{// 找出最大最小值int min = arr[0];int max = arr[0];for (int i = 1;i < n;i++){if (arr[i] > max)max = arr[i];if (arr[i] < min)min = arr[i];}// 创建计数的空间int range = max - min + 1;int* countArr = (int*)malloc(sizeof(int) * range);memset(countArr, 0, sizeof(int) * range); // 将数组元素置为0// 遍历数组将相同的数值出现的次数放到相对位置处：arr[i] - minfor (int i = 0;i < n;i++){countArr[arr[i] - min]++;}// 遍历countArr数组将某个数出现的次数，依次将这个数放回到原数组int index = 0;for (int i = 0;i < range;i++){while (countArr[i]--)  // 控制数据出现的次数{arr[index++] = i + min;}}
}void TestCountSort()
{int arr[] = { 15,18,23,3,1,14,2,8,4,9,6,0,7 };CountSort(arr, sizeof(arr) / sizeof(arr[0]));Printarry(arr, sizeof(arr) / sizeof(arr[0]));
}
int main()
{TestCountSort();return 0;
}

查看全文

http://www.xdnf.cn/news/1111141.html