目录

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;
}