插入、希尔、冒泡、选择排序

目录

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