// 冒泡排序
// 选择排序
// 希尔排序
// 快速排序
// 递归排序
// 堆排序
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <sys/timeb.h>
#define MAX 40000
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;
}
void MySwap(int arr[], int a, int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
//创建数组
int* CreateArray()
{
srand((unsigned int)time(NULL));
int* arr = (int*)malloc(sizeof(int)*MAX);
for (int i = 0; i < MAX; i++)
{
arr[i] = rand() % MAX;
}
return arr;
}
void PrintArray(int arr[], int length)
{
for (size_t i = 0; i < length; i++)
{
printf("%d ", arr[i]);
}
printf("
");
}
// 冒泡排序
void BubbleSort(int arr[], int length)
{
for (size_t i = 0; i < length; i++)
{
for (size_t j = i + 1; j < length; j++)
{
if (arr[i] < arr[j])
{
Swap(&arr[i], &arr[j]);
}
}
}
}
// 选择排序
void SelectSort(int arr[], int length)
{
int min = 0;
for (int i = 0; i < length; i++)
{
for (size_t j = i + 1; j < length; j++)
{
if (arr[j] < arr[min])
{
min = j;
}
}
if (min != i)
{
Swap(&arr[min], &arr[i]);
}
}
}
// 希尔排序
void ShellSort(int arr[], int length)
{
int increasement = length;
int i, j, k;
do {
//确定分组的增量
increasement = increasement / 3 + 1;
for (i = 0; i < increasement; i++)
{
for (j = i + increasement; j < length; j += increasement)
{
if (arr[j] < arr[j - increasement])
{
int temp = arr[j];
for (k = j - increasement; k >= 0 && temp < arr[k]; k -= increasement)
{
arr[k + increasement] = arr[k];
}
arr[k + increasement] = temp;
}
}
}
} while (increasement > 1);
}
int partition(int arr[], int low, int high) {
int key;
key = arr[low];
while (low<high) {
while (low <high && arr[high] >= key)
high--;
if (low<high)
arr[low++] = arr[high];
while (low<high && arr[low] <= key)
low++;
if (low<high)
arr[high--] = arr[low];
}
arr[low] = key;
return low;
}
void quick_sort(int arr[], int start, int end) {
int pos;
if (start<end) {
pos = partition(arr, start, end);
quick_sort(arr, start, pos - 1);
quick_sort(arr, pos + 1, end);
}
return;
}
// 快速排序
void QuickSort(int arr[], int start, int end)
{
int i = start;
int j = end;
//基准数
int temp = arr[start];
if (i < j)
{
while (i < j)
{
while (i < j && arr[j] >= temp)
{
j--;
}
if (i < j)
{
arr[i] = arr[j];
i++;
}
while (i < j && arr[i] < arr[temp])
{
i++;
}
if (i < j)
{
arr[j] = arr[i];
j--;
}
}
arr[i] = temp;
QuickSort(arr, start, i - 1);
QuickSort(arr, i + 1, end);
}
}
// 合并算法
void Merge(int arr[], int start, int end, int mid, int* temp)
{
int i_start = start;
int i_end = mid;
int j_start = mid + 1;
int j_end = end;
// 表示辅助空间有多少个元素
int length = 0;
// 合并两个有序序列
while (i_start <= i_end && j_start <= j_end)
{
if (arr[i_start] < arr[j_start])
{
temp[length] = arr[i_start];
length++;
i_start++;
}
else
{
temp[length] = arr[j_start];
length++;
j_start++;
}
}
// i这个序列
while (i_start <= i_end)
{
temp[length] = arr[i_start];
length++;
i_start++;
}
while (j_start <= j_end)
{
temp[length] = arr[j_start];
length++;
j_start++;
}
// 辅助空间数据覆盖到原空间
for (int i = 0; i < length; i++)
{
arr[start + i] = temp[i];
}
}
//归并排序
void MergeSort(int arr[], int start, int end, int* temp)
{
if (start >= end)
{
return;
}
int mid = (start + end) / 2;
MergeSort(arr, start, mid, temp);
MergeSort(arr, mid + 1, end, temp);
Merge(arr, start, end, mid, temp);
}
/*
@param arr 待调整的数组
#param index 待调整的节点的下标
@param len 数组长度
*/
void HeapAdjust(int arr[], int index, int length)
{
// 保存当前节点下标
int max = index;
// 保存子节点的数组下标
int lchild = index * 2 + 1;
int rchild = index * 2 + 2;
if (lchild < length && arr[lchild] > arr[max])
{
max = lchild;
}
if (rchild<length&& arr[rchild]>arr[max])
{
max = rchild;
}
if (max != index)
{
MySwap(arr, max, index);
HeapAdjust(arr, max, length);
}
}
void HeapSort(int arr[], int length)
{
// 初始化堆
for (int i = length / 2 - 1; i >= 0; i--)
{
HeapAdjust(arr, i, length);
}
// 交换堆顶元素和最后一个元素
for (int i = length - 1; i >= 0; i--)
{
MySwap(arr, 0, i);
HeapAdjust(arr, 0, i);
}
}
int main(void)
{
int* arr_bubble = CreateArray();
int* arr_select = CreateArray();
int* arr_shell = CreateArray();
int* arr_quick = CreateArray();
int* arr_merge = CreateArray();
int* arr_heap = CreateArray();
long tbubble_start = 0;
long tbubble_end = 0;
// 冒泡排序
//PrintArray(arr_bubble, MAX);
tbubble_start = getSystemTime();
BubbleSort(arr_bubble, MAX);
tbubble_end = getSystemTime();
//PrintArray(arr_bubble, MAX);
printf("冒泡排序%d个数,所需时间:%d
", MAX, tbubble_end - tbubble_start);
printf("---------------------------------------
");
// 选择排序
//PrintArray(arr_select, MAX);
tbubble_start = getSystemTime();
SelectSort(arr_select, MAX);
tbubble_end = getSystemTime();
//PrintArray(arr_select, MAX);
printf("选择排序%d个数,所需时间:%d
", MAX, tbubble_end - tbubble_start);
printf("---------------------------------------
");
// 希尔排序
//PrintArray(arr_shell, MAX);
tbubble_start = getSystemTime();
ShellSort(arr_shell, MAX);
tbubble_end = getSystemTime();
//PrintArray(arr_shell, MAX);
printf("希尔排序%d个数,所需时间:%d
", MAX, tbubble_end - tbubble_start);
printf("---------------------------------------
");
// 快速排序
int start = 0;
int end = MAX-1;
//PrintArray(arr_quick, MAX);
tbubble_start = getSystemTime();
quick_sort(arr_quick, start, end);
tbubble_end = getSystemTime();
//PrintArray(arr_quick, MAX);
printf("快速排序%d个数,所需时间:%d
", MAX, tbubble_end - tbubble_start);
printf("---------------------------------------
");
// 递归排序
//PrintArray(arr_merge, MAX);
tbubble_start = getSystemTime();
int* arr_temp = (int*)malloc(sizeof(int)*MAX);
MergeSort(arr_merge, 0, MAX - 1, arr_temp);
tbubble_end = getSystemTime();
//PrintArray(arr_merge, MAX);
printf("递归排序%d个数,所需时间:%d
", MAX, tbubble_end - tbubble_start);
printf("---------------------------------------
");
// 堆排序
//PrintArray(arr_heap, MAX);
tbubble_start = getSystemTime();
HeapSort(arr_heap, MAX);
tbubble_end = getSystemTime();
//PrintArray(arr_heap, MAX);
printf("堆排序%d个数,所需时间:%d
", MAX, tbubble_end - tbubble_start);
free(arr_temp);
free(arr_bubble);
free(arr_select);
free(arr_shell);
free(arr_quick);
free(arr_merge);
return 0;
}