插入、希尔、冒泡、选择排序
目录
1.插入排序
2.希尔排序
3.冒泡排序
4.选择排序
5.完整代码以及时间测试
1.插入排序
即每次把要插入的元素插入已经有序的数组中，经过不断向前比较，来插入目标元素
void InsertSort(int* a, int n)
{
for (int i = 0; i < n-1;i++)
{
int end = i;
int insert = a[i+1];
while (end >= 0)
{
if (insert < a[end])
{
a[end + 1] = a[end];
}
else
{
break;
}
end--;
}
a[end + 1] = insert;
}
}2.希尔排序
有两个阶段
1.预排序，间隔gap的个元素分为一组，一共gap组。目的是尽量将数组变为有序
（当gap为1的时候即为插入排序）
2.改变gap，重复进行预排序，进一步将数组变为有序
3.插入排序
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; i++)//和下面的原理一样但是比下面的少写一个循环
//下面是一组比完比下一组，这个是先将每一组的相邻先比较，一直到结束，并驾齐驱
{
int end = i;
int insert = a[i + gap];
while (end >= 0)
{
if (insert < a[end])
{
a[end + gap] = a[end];
}
else
{
break;
}
end -= gap;
}
a[end + gap] = insert;
}
}
//int gap = n;
//while (gap > 1)
//{
// gap = gap / 3 + 1;
// for (int j = 0; j < gap; j++)
// {
// for(int i = j; i < n - gap; i += gap)
// {
// int end = i;
// int insert = a[i + gap];
// while (end >= 0)
// {
// if (insert < a[end])
// {
// a[end + gap] = a[end];
// }
// else
// {
// break;
// }
// end -= gap;
// }
// a[end + gap] = insert;
// }
// }
//}
}时间复杂度的计算复杂且涉及到一些未解决的数学问题，这里只简单分析
最外层一层while循环时间复杂度大约是log3N
当gap为一个很大的值时，例如n/3，就有n/3组，按照每组元素个数相等，每组最坏的情况下，要进行1+2+3次置换，那么时间复杂度约为2N，即O(n)的时间复杂度
当gap为1时候，最坏情况下，时间复杂度理论上为1+2+3+4+....+n-1，但是因为已经进行过预排序，所以整个数组几乎是有序的，时间复杂度也是O(n)层次
一般我们认为希尔排序的时间复杂度为O(n^1.3)
3.冒泡排序
从第一个元素开始，将这个元素和后面的元素比较，若更大，交换两个元素，一直到末尾，这样一次排序后最后一个元素必定为最大元素。
重复以上操作，将结束位置不断减小,一直到1，进行最后一次置换之后，数组即有序.
void myswap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n; j++)
{
bool flag = false;
for(int i= 1; i < n - j; i++)
{
if (a[i - 1] > a[i])
{
myswap(&a[i - 1], &a[i]);
flag = true;
}
}
if (flag == false)
{
break;
}
}
}4.选择排序
每一次找出最大和最小的与两段元素交换
void myswap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int mini = begin;
int maxi = end;
for (int i = begin; i <= end; i++)
{
if(a[i] < a[mini])mini = i;
if(a[i] > a[maxi])maxi = i;
}
myswap(&a[begin], &a[mini]);
if (begin == maxi)
{
maxi = mini;
}
myswap(&a[end], &a[maxi]);
end--;
begin++;
}
}这里涉及到当begin正好等于maxi的情况，我们进行特判，因为我们把该下标对应元素换到mini下标的位置，所以再重新存入该下标
5.完整代码以及时间测试
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<time.h>
#include <malloc.h>
#include<stdlib.h>
using namespace std;
// 插入排序
void InsertSort(int* a, int n)
{
for (int i = 0; i < n-1;i++)
{
int end = i;
int insert = a[i+1];
while (end >= 0)
{
if (insert < a[end])
{
a[end + 1] = a[end];
}
else
{
break;
}
end--;
}
a[end + 1] = insert;
}
}
// 希尔排序
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; i++)//和下面的原理一样但是比下面的少写一个循环
//下面是一组比完比下一组，这个是先将每一组的相邻先比较，一直到结束，并驾齐驱
{
int end = i;
int insert = a[i + gap];
while (end >= 0)
{
if (insert < a[end])
{
a[end + gap] = a[end];
}
else
{
break;
}
end -= gap;
}
a[end + gap] = insert;
}
}
//int gap = n;
//while (gap > 1)
//{
// gap = gap / 3 + 1;
// for (int j = 0; j < gap; j++)
// {
// for(int i = j; i < n - gap; i += gap)
// {
// int end = i;
// int insert = a[i + gap];
// while (end >= 0)
// {
// if (insert < a[end])
// {
// a[end + gap] = a[end];
// }
// else
// {
// break;
// }
// end -= gap;
// }
// a[end + gap] = insert;
// }
// }
//}
}
void myswap(int* a, int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n; j++)
{
bool flag = false;
for(int i= 1; i < n - j; i++)
{
if (a[i - 1] > a[i])
{
myswap(&a[i - 1], &a[i]);
flag = true;
}
}
if (flag == false)
{
break;
}
}
}
void SelectSort(int* a, int n)
{
int begin = 0;
int end = n - 1;
while (begin < end)
{
int mini = begin;
int maxi = end;
for (int i = begin; i <= end; i++)
{
if(a[i] < a[mini])mini = i;
if(a[i] > a[maxi])maxi = i;
}
myswap(&a[begin], &a[mini]);
if (begin == maxi)
{
maxi = mini;
}
myswap(&a[end], &a[maxi]);
end--;
begin++;
}
}
void printfarr(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
void inserttest()
{
int arr[] = {5,9,6,1,3,7,2,5};
printfarr(arr, sizeof(arr) / sizeof(int));
InsertSort(arr, sizeof(arr) / sizeof(int));
printfarr(arr, sizeof(arr) / sizeof(int));
}
void shelltest()
{
int arr[] = { 5,9,6,1,3,7,2,5 };
printfarr(arr, sizeof(arr) / sizeof(int));
ShellSort(arr, sizeof(arr) / sizeof(int));
printfarr(arr, sizeof(arr) / sizeof(int));
}
void bubbletest()
{
int arr[] = { 5,9,6,1,3,7,2,5 };
printfarr(arr, sizeof(arr) / sizeof(int));
BubbleSort(arr, sizeof(arr) / sizeof(int));
printfarr(arr, sizeof(arr) / sizeof(int));
}
void selecttest()
{
int arr[] = { 5,9,6,1,3,7,2,5 };
printfarr(arr, sizeof(arr) / sizeof(int));
SelectSort(arr, sizeof(arr) / sizeof(int));
printfarr(arr, sizeof(arr) / sizeof(int));
}
int main()
{
srand(time(0));
int n = 100000;
int* arr1 = (int*)malloc(sizeof(int)* n);
int* arr2 = (int*)malloc(sizeof(int) * n);
int* arr3 = (int*)malloc(sizeof(int) * n);
int* arr4 = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++)
{
arr1[i] = arr2[i] = arr3[i] = arr4[i] = rand();
}
int begin1 = clock();
InsertSort(arr1,n);
int end1 = clock();
int begin2 = clock();
ShellSort(arr2,n);
int end2 = clock();
int begin3 = clock();
BubbleSort(arr3,n);
int end3 = clock();
int begin4 = clock();
SelectSort(arr4,n);
int end4 = clock();
printf("insertsort:%d\n", end1 - begin1);
printf("shellsort:%d\n", end2 - begin2);
printf("bubblesort:%d\n", end3 - begin3);
printf("selectsort:%d\n", end4 - begin4);
return 0;
}