文章目录
- 前言
- 打印数组函数
- 一、插入排序
- 二、希尔排序
- 三、选择排序
- 四、堆排序
- 五、冒泡排序
- 总结
前言
C语言数据结构排序、插入排序、希尔排序（多组并排、一组排完排另一组）、选择排序、堆排序、冒泡排序等的介绍
打印数组函数
打印数组函数定义
// 打印数组
void PrintArray(int* a, int n)
{
int i = 0;
for (i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
一、插入排序
插入排序定义
// 插入排序------升序
void InsertSort(int* a, int n)
{
int i = 0;
for (i = 1; i < n; i++)
{
int end = i - 1;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
插入排序测试
void TestInsertSort()
{
int a[] = { 9, 6, 5, 7, 3, 1, 4, 2, 8, 0 };
int sz = sizeof(a) / sizeof(a[0]);
PrintArray(a, sz);
InsertSort(a, sz);
PrintArray(a, sz);
}
效果如下：
二、希尔排序
-
希尔排序的思想是先分组，进行预排序，使数组趋向于有序。
-
然后进行逐步减小分组的跨度，直至分组跨度为1，变为有序排序。
-
如上图所示，先进行分组，在组内进行排序。
-
希尔排序可以有两种方式
- 一组排完再排另一组
希尔排序定义
// 希尔排序
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap /= 2;
int j = 0;
for (j = 0; j < gap; j++)
{
int i = 0;
for (i = gap + j; i < n; i += gap)
{
int end = i - gap;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
}
希尔排序测试
void TestShellSort()
{
int a[] = { 9, 7, 6 ,4 ,8 ,3 ,5 ,1 ,2, 0 };
PrintArray(a, sizeof(a) / sizeof(a[0]));
ShellSort(a, sizeof(a) / sizeof(a[0]));
PrintArray(a, sizeof(a) / sizeof(a[0]));
}
效果如下：
- 多组并排----每次排一组的一个数
希尔排序定义
// 希尔排序---- 多组并排
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap /= 2;
int i = 0;
for (i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
希尔排序测试
void TestShellSort()
{
int a[] = { 9, 7, 6 ,4 ,8 ,3 ,5 ,1 ,2, 0 };
PrintArray(a, sizeof(a) / sizeof(a[0]));
ShellSort(a, sizeof(a) / sizeof(a[0]));
PrintArray(a, sizeof(a) / sizeof(a[0]));
}
效果如下：
- 希尔排序的时间复杂度差不多是 O(N1.3 ).
三、选择排序
选择排序定义
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
// 选择排序
void SelectSort(int* a, int n)
{
int left = 0;
int right = n - 1;
while (left < right)
{
int maxi = left;
int mini = left;
int i = 0;
for (i = left + 1; i <= right; i++)
{
if (a[i] < a[mini])
mini = i;
if (a[i] > a[maxi])
maxi = i;
}
Swap(&a[left], &a[mini]);
if (left == maxi)
{
maxi = mini;
}
Swap(&a[right], &a[maxi]);
left++;
right--;
}
}
选择排序测试
void TestSelectSort()
{
int a[] = { 9, 2, 6, 8, 4, 7, 5, 3, 1, 0 };
int sz = sizeof(a) / sizeof(a[0]);
PrintArray(a, sz);
SelectSort(a, sz);
PrintArray(a, sz);
}
效果如下：
四、堆排序
堆排序定义
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
// 向下调整建堆
// 升序建大堆
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child] < a[child + 1])
{
child++;
}
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
}
parent = child;
child = parent * 2 + 1;
}
}
// 堆排序
void HeapSort(int* a, int n)
{
// 建堆----向下调整建堆
int i = 0;
for(i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
// 堆排序
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
end--;
AdjustDown(a, end+1, 0);
}
}
堆排序测试
void TestHeapSort()
{
int a[] = { 9, 2, 6, 8, 4, 7, 5, 3, 1, 0 };
int sz = sizeof(a) / sizeof(a[0]);
PrintArray(a, sz);
HeapSort(a, sz);
PrintArray(a, sz);
}
效果如下：
五、冒泡排序
冒泡排序定义
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
// 冒泡排序
void BubbleSort(int* a, int n)
{
int j = 0;
for (j = 0; j < n - 1; j++)
{
int i = 0;
for (i = 0; i < n - 1- j; i++)
{
if (a[i] > a[i + 1])
{
Swap(&a[i], &a[i + 1]);
}
}
}
}
冒泡排序测试
void TestBubbleSort()
{
int a[] = { 9, 2, 6, 8, 4, 7, 5, 3, 1, 0 };
int sz = sizeof(a) / sizeof(a[0]);
PrintArray(a, sz);
BubbleSort(a, sz);
PrintArray(a, sz);
}
效果如下：
总结
C语言数据结构排序、插入排序、希尔排序（多组并排、一组排完排另一组）、选择排序、堆排序、冒泡排序等的介绍
