排序的基本概念
冒泡排序
示例：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<sys/timeb.h>
#define MAX 10000
long getSystemTime()
{
struct timeb tb;
ftime(&tb);//取系统的时间，精确到毫秒，其返回一个结构体
return tb.time * 1000 + tb.millitm;//将秒转换成毫秒，转换单位为1000，millitm表示毫秒
}
//交换函数
//void Swap(int* a, int* b)
//{
// int temp = *a;
// *a = *b;
// *b = temp;
//}
//冒泡排序
void BubbleSort(int arr[], int length)
{
for (int i = 0; i < length - 1; i++)
{
for (int j = 0; j < length - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
/*Swap(&arr[j], &arr[j + 1]);*/
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
改进的冒泡排序
//int flag = 0;//表示没有排序好
//void BubbleSort(int arr[], int length)
//{
// for (int i = 0; i < length - 1; i++)
// {
// flag = 1;//认为已经排序好
// for (int j = 0; j < length - i - 1; j++)
// {
// if (arr[j] > arr[j + 1])
// {
// flag = 0;
// /*Swap(&arr[j], &arr[j + 1]);*/
// int temp = arr[j];
// arr[j] = arr[j + 1];
// arr[j + 1] = temp;
// }
// }
// }
//}
//打印函数
void PrintArray(int arr[], int length)
{
for (int i = 0; i < length; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
int main()
{
int arr[MAX];
srand((unsigned int)time(NULL));//随机种子
for (int i = 0; i < MAX; i++)
{
arr[i] = rand() % MAX;
}
printf("排序前：\n");
//PrintArray(arr, MAX);
long t_start = getSystemTime();
BubbleSort(arr, MAX);
long t_end = getSystemTime();
printf("冒泡排序%d个元素所需的时间是%d\n", MAX, t_end - t_start);
//PrintArray(arr, MAX);
return 0;
}
结果：
冒泡排序10000个元素所需的时间是179
选择排序
示例：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<sys/timeb.h>
#include<time.h>
#define MAX 10000
long getSystemTime()
{
struct timeb tb;
ftime(&tb);//取系统的时间，精确到毫秒，其返回一个结构体
return tb.time * 1000 + tb.millitm;//将秒转换成毫秒，转换单位为1000，millitm表示毫秒
}
//交换函数
void Swap(int* a, int* b)
{
int temp = *a;
*a = *b;
*b = temp;
}
//打印函数
void PrintArray(int arr[], int length)
{
for (int i = 0; i < length; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
//改进的冒泡排序
int flag = 0;//表示没有排序好
void bubblesort(int arr[], int length)
{
for (int i = 0; i < length - 1; i++)
{
flag = 1;//认为已经排序好
for (int j = 0; j < length - i - 1; j++)
{
if (arr[j] > arr[j + 1])
{
flag = 0;
/*swap(&arr[j], &arr[j + 1]);*/
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
//选择排序,只是减少交换次数
void SelectSort(int arr[],int length)
{
for (int i = 0; i < length-1; i++)
{
int min = i;
for (int j = i + 1; j < length; j++)
{
if (arr[j] < arr[min])
{
min = j;
}
}
if (min != i)
{
Swap(&arr[min], &arr[i]);
}
}
}
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;
}
//冒泡排序时间计算
long tbubble_start = getSystemTime();
bubblesort(arr, MAX);
long tbubble_end = getSystemTime();
printf("冒泡排序%d个数，所用总时间为：%d\n", MAX, tbubble_end- tbubble_start);
//选择排序时间计算
long tselect_start = getSystemTime();
SelectSort(arr2, MAX);
long tselect_end = getSystemTime();
printf("选择排序%d个数，所用总时间为：%d\n", MAX, tselect_end- tselect_start);
//PrintArray(arr2,MAX);
return 0;
}
结果：
冒泡排序10000个数，所用总时间为：177
选择排序10000个数，所用总时间为：94
插入排序
☆ 将无序序列插入到有序序列中。
示例：
# include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<sys/timeb.h>
#define MAX 10000
//计算系统时间
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;
}
//打印函数
PrintArray(int arr[], int length)
{
for (int i = 0; i < length; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
//选择排序,只是减少交换次数
void SelectSort(int arr[], int length)
{
for (int i = 0; i < length - 1; i++)
{
int min = i;
for (int j = i + 1; j < length; j++)
{
if (arr[j] < arr[min])
{
min = j;
}
}
if (min != i)
{
Swap(&arr[min], &arr[i]);
}
}
}
//插入排序
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 && arr[j] > temp; j--)//将待插入的数与前面的有序序列挨个进行比较
{
arr[j + 1] = arr[j];
}
arr[j+1] = temp;//将带插入的数与前面所有的有序序列比较完后，在将待插入的数放入。
}
}
}
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;
}
//选择排序时间计算
long tselect_start = getSystemTime();
SelectSort(arr2, MAX);
long tselect_end = getSystemTime();
printf("选择排序%d个数，所用总时间为：%d\n", MAX, tselect_end - tselect_start);
//PrintArray(arr2,MAX);
//插入排序
long tInsert_start = getSystemTime();
//PrintArray(arr, MAX);
InsertSort(arr, MAX);
long tInsert_end = getSystemTime();
//PrintArray(arr, MAX);
printf("插入排序%d个数，所有时间为%d\n", MAX, tInsert_end - tInsert_start);
}
结果：
选择排序10000个数，所用总时间为：96
插入排序10000个数，所有时间为49
希尔排序
☆ 数据量非常大时希尔排序很有优势。
示例：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<sys/timeb.h>
# define MAX 100000
//计算系统时间
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 PrintArray(int arr[],int length)
{
for (int i = 0; i < length; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
//插入排序
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 && arr[j] > temp; j--)//将待插入的数与前面的有序序列挨个进行比较
{
arr[j + 1] = arr[j];
}
arr[j + 1] = temp;//将带插入的数与前面所有的有序序列比较完后，在将待插入的数放入。
}
}
}
//希尔排序
void ShellSort(int arr[], int length)
{
int i, j, k;
//确定分组的增量
int increasement = length;
do
{
increasement = increasement / 3 + 1;
for (i = 0; i < increasement; i++)//i代表的是组数
{
for (j = i + increasement; j < length; j += increasement)//j代表每一组的各个数
{
if (arr[j] < arr[j - increasement])
{
int temp = arr[j];
for (k = j - increasement; k >=0 && arr[k] > temp; k -= increasement)//k代表的是每组前面有序的k个元素
{
arr[k + increasement] = arr[k];
}
arr[k + increasement] = temp;
}
}
}
} while (increasement > 1);
}
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;
}
//插入排序时间
long tInsert_start = getSystemTime();
//PrintArray(arr, MAX);
InsertSort(arr2, MAX);
long tInsert_end = getSystemTime();
//PrintArray(arr, MAX);
printf("插入排序%d个数，所有时间为%d\n", MAX, tInsert_end - tInsert_start);
//希尔排序的时间
long tshell_start = getSystemTime();
//PrintArray(arr, MAX);
ShellSort(arr, MAX);
//PrintArray(arr, MAX);
long tshell_end = getSystemTime();
printf("希尔排序%d个数，所需总时间为%d\n", MAX, tshell_end - tshell_start);
return 0;
}
结果：
插入排序100000个数，所有时间为4881
希尔排序100000个数，所需总时间为15
快速排序
☆ 排序最快的
- 将第一个元素设置为基准数。
- 将第一个位置设置为i，最后一个位置设置为j
- 从右找比基准数小的 ，往前挪；从左找比基准数大的，往后挪。
- 当i和j相等后，将基准数放到这个位置。
- 则一次比较结束，然后按基准数分为左右两部分，分别进行上述步骤，不断缩小范围。
示例：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<sys/timeb.h>
#define MAX 100000
long getSyatemTime()
{
struct timeb tb;
ftime(&tb);
return tb.time * 1000 + tb.millitm;
}
void PrintArray(int arr[],int length)
{
for (int i = 0; i < length;i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
//快速排序,从小到大
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] < temp)
i++;
if (i < j)//填坑
{
arr[j] = arr[i];
j--;
}
}
//把基准数放到i的位置
arr[i] = temp;
//使用递归，对左半部分进行快速排序
QuickSort(arr, start, i - 1);
//对右半部分进行快速排序
QuickSort(arr, i + 1, end);
}
}
int main()
{
/*int myArr[] = { 4,2,8,0,5,7,1,3,9 };
int length = sizeof(myArr) / sizeof(int);*/
int arr[MAX];
srand((unsigned int)time(NULL));
for (int i = 0; i < MAX; i++)
{
arr[i] = rand() % MAX;
}
long tquick_start = getSyatemTime();
//PrintArray(arr,MAX);
QuickSort(arr,0,MAX-1);
//PrintArray(arr,MAX);
long tquick_end = getSyatemTime();
printf("快速排序%d个数，所需的总时间是%d\n", MAX, tquick_end - tquick_start);
return 0;
}
结果：
快速排序100000个数，所需的总时间是11
归并排序
1. 基本思想
归并排序是用分治思想，分治模式在每一层递归上有三个步骤：
分解（Divide）：将n个元素分成个含n/2个元素的子序列。
解决（Conquer）：用合并排序法对两个子序列递归的排序。
合并（Combine）：合并两个已排序的子序列已得到排序结果。
2. 实现逻辑
迭代法
① 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
② 设定两个指针，最初位置分别为两个已经排序序列的起始位置
③ 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
④ 重复步骤③直到某一指针到达序列尾
⑤ 将另一序列剩下的所有元素直接复制到合并序列尾
递归法
① 将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素
② 将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素
③ 重复步骤②，直到所有元素排序完毕
☆ 需要格外的空间存放每一次合并后的结果，使用完后销毁，以空间换时间。
示例：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<sys/timeb.h>
#define MAX 100000
//系统时间
long getSystemTime()
{
struct timeb tb;
ftime(&tb);
return tb.time * 1000 + tb.millitm;
}
//创建数组
int* CreateArray()
{
int* arr = (int*)malloc(sizeof(int)*MAX);
srand((unsigned int)time(NULL));
for (int i = 0; i < MAX; i++)
{
arr[i] = rand() % MAX;
}
return arr;
}
//打印
void PrintArray(int arr[], int length)
{
for (int i = 0; i < length; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
//合并算法 从大到小
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];
j_start++;
length++;
}
}
//i这个序列
while (i_start <= i_end)
{
temp[length] = arr[i_start];
i_start++;
length++;
}
//j这个序列
while (j_start <= j_end)
{
temp[length] = arr[j_start];
j_start++;
length++;
}
//辅助空间数据覆盖原空间
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);
}
int main()
{
int* myArr = CreateArray();
//PrintArray(myArr, MAX);
//辅助空间
int* temp = (int*)malloc(sizeof(int)*MAX);
long tmerge_start = getSystemTime();
MergeSort(myArr, 0, MAX - 1,temp);
long tmerge_end = getSystemTime();
//PrintArray(myArr, MAX);
printf("归并排序%d个数，所需总时间为%d\n", MAX, tmerge_end - tmerge_start);
//释放空间
free(temp);
free(myArr);
return 0;
}
结果：
归并排序100000个数，所需总时间为17
堆排序
☆ 堆排序就是调整堆的过程。
☆ 初始化堆的时候，从下往上调整 i=len/2 i–
☆ 调整堆的时候，从上往下调整
示例：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>
#include<sys/timeb.h>
#define MAX 100000
//系统时间
long getSystemTime()
{
struct timeb tb;
ftime(&tb);
return +tb.time * 1000+tb.millitm;
}
//打印
void PrintArray(int arr[],int length)
{
for (int i = 0; i < length; i++)
{
printf("%d ", arr[i]);
}
printf("\n");
}
//交换
void Swap(int arr[], int a, int b)
{
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
//调整堆
//myArr 待调整的数组
//index 待调整的结点下标
//len 数组的长度
void HeapAdjust(int arr[], int index, int len)
{
int max = index;
int lchild = index * 2 + 1;
int rchild = index * 2 + 2;
if (lchild<len&&arr[max] < arr[lchild])
{
max = lchild;
}
if (rchild < len&&arr[max] < arr[rchild])
{
max = rchild;
}
if (max != index)
{
Swap(arr, max, index);
HeapAdjust(arr, max, len);
}
}
//堆排序
void HeapSort(int myArr[], int len)
{
//初始化堆，大顶堆，从小到大
for (int i = len / 2 - 1; i >= 0; i--)
{
HeapAdjust(myArr,i,len);
}
//交换堆顶元素和最后一个元素
for (int i = len - 1; i > 0; i--)
{
Swap(myArr, 0, i);
HeapAdjust(myArr, 0, i);
}
}
int main()
{
int arr[MAX];
srand((unsigned int)time( NULL));
for (int i = 0; i < MAX; i++)
{
arr[i] = rand() % MAX;
}
//int myArr[] = { 4,2,8,0,5,7,1,3,9 };
//int len = sizeof(myArr) / sizeof(int);
long theap_start = getSystemTime();
//PrintArray(arr,MAX );
//堆排序
HeapSort(arr,MAX);
long theap_end= getSystemTime();
//PrintArray(arr,MAX);
printf("堆排序%d个数，所用总时间为%d\n", MAX, theap_end - theap_start);
return 0;
}
结果：
堆排序100000个数，所用总时间为66