c语言希尔排序总结(详解)
2023-12-13 19:43:52
希尔排序:
1:分组插入排序两两分组降低元素个数提高插入的效率,先分组对每一组分别进行插入排序
希尔排序是插入排序的一种改进算法,也称为缩小增量排序。其基本原理是通过将待排序的序列分成若干个子序列,对每个子序列进行插入排序,然后逐渐缩小子序列的间隔,直到整个序列基本有序。
希尔排序的原理如下:
- 首先确定一个增量序列,通常是使用希尔增量序列(例如:N/2, N/4, N/8, … 1),其中N为待排序序列的长度。
- 按照增量序列的间隔,将待排序序列分成若干个子序列。
- 对每个子序列分别进行插入排序。
- 缩小增量,重复步骤2和步骤3,直到增量为1。
- 最后进行一次插入排序,确保整个序列有序。
希尔排序的时间复杂度取决于增量序列的选择,一般情况下为O(n1.3)至O(n2)之间。希尔排序是一种不稳定的排序算法,因为在排序过程中会涉及多次元素交换。希尔排序相对于简单的插入排序来说,具有更好的时间性能,尤其在大规模数据的情况下,相对于其他O(n^2)的排序算法也有更好的性能。
希尔排序代码截图:
希尔排序详细代码:
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string.h>
#include <time.h>
#include <sys/timeb.h>
#define MAX 10
// 获取当前系统的时间
long getSystemTime() {
struct timeb tb;
ftime(&tb);
return tb.time * 1000 + tb.millitm;
}
// 交换函数
void Swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int flag = 0; // 表示没有排序好
//插入排序实现的代码
void InsertSort(int arr[], int length) {
int j;
for (int i = 1; i < length; i++) {
// 用当前这个数和前面的这个数进行比较
if (arr[i] < arr[i - 1]) {
// 插入排序,给数据做一个缓存
int temp = arr[i];
for (j = i - 1; j >= 0 && temp < arr[j];j--) {
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;
}
}
}
// 希尔排序代码的实现
void ShellSort(int arr[], int length) {
//
int inceeasement = length;
int i;
int j;
int k;
do {
// 循环第一步确定循环的增量
inceeasement = inceeasement / 3 + 1;
for (i = 0; i < inceeasement; i++) {
// 确定每一组的第一个元素
for (j = i + inceeasement; j < length; j += inceeasement) {
if (arr[j] < arr[j - inceeasement]) {
// 缓存数据
int temp = arr[j];
for (k = j - inceeasement; k >= 0 && temp < arr[k];k-= inceeasement) {
arr[k + inceeasement] = arr[k];
}
arr[k + inceeasement] = temp;
}
}
}
} while (inceeasement > 1);
}
// 打印函数
void PrintArray(int arr[], int length) {
for (int i = 0; i < length; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[MAX];
int arr2[MAX];
srand((unsigned int)time(NULL));
for (int i = 0; i < MAX; i++) {
int randNum = rand() % MAX;
arr[i] = randNum;
arr2[i] = randNum;
}
PrintArray(arr, MAX);
//插入排序
long InsertSort_start = getSystemTime();
InsertSort(arr, MAX);
PrintArray(arr, MAX);
long InsertSort_end = getSystemTime();
printf("插入排序%d个元素所需要的时间:%ld\n", MAX, InsertSort_end - InsertSort_start);
PrintArray(arr2, MAX);
// 希尔排序
long ShellSort_start = getSystemTime();
ShellSort(arr2, MAX);
PrintArray(arr2, MAX);
long ShellSort_end = getSystemTime();
printf("希尔排序%d个元素所需要的时间:%ld\n", MAX, ShellSort_end - ShellSort_start);
return 0;
}
希尔排序运行结果展示
文章来源:https://blog.csdn.net/qq_45973003/article/details/134898131
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!