数据结构：七种排序及总结

排序

我们数据结构常见的排序有四大种，四大种又分为七小种，如图所示

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次
序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排
序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不断地在内外存之间移动数据的排序。

一插入排序

1直接插入排序

void InsertSort(int* a, int n);

从i=0开始遍历，每次i之前的序列都是有序的，通过判断当前i的值能够在i之前哪个位置，找到后直接插入，

为什么直接插入排序最坏的情况是n^2？
如果一个开始原序列是降序，想排为升序
第一个循环是n，第二个循环最坏是n，所以是最大n^2

void InsertSort(int* arr, int n) {for (int i = 0; i < n-1; i++) {int end = i;int tem = arr[end + 1];while (end >= 0) {if (arr[end] > tem) {arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tem;}}

2希尔排序

希尔排序是对直接插入排序的优化，大大优化了时间复杂度
他们是先规定了一个gap值，然后每次进行循环把gap值缩小，最后把 gap值调为1。这样最后一次排序就是直接插入排序，前面的是预排序。
条件就是

while(gap>1){
gap=gap/3+1;//最后一次gap=1随后跳出循环}

void ShellSort(int* arr, int n) {int gap = n;while(gap>1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++) {int end = i;int tem = arr[end +gap];while (end >= 0) {if (arr[end] > tem) {arr[end + gap] = arr[end];end-=gap;}else{break;}}arr[end + gap] = tem;}	}}

判断两种排序的时间复杂度

二选择排序

3直接选择排序

直接选择排序就是一种很暴力的解法，思路简单，代码简单，但是时间复杂度很差，和 冒泡排序差不多

思路就是分别从两头找最大和最小，然后对下标进行++ – 然后直到相遇。

void SeletSort(int* arr, int n) {int end = n - 1;int begin = 0;int max, min;max = min = 0;while (begin < end) {max = min = begin;for (int i = begin + 1; i <= end; i++){if (arr[i] > arr[max]) {max = i;}if (arr[i] < arr[min]){min = i;}}if (max == begin) {max = min;}Swap(&arr[min], &arr[begin]);Swap(&arr[max], &arr[end]);begin++;end--;}}

有一种特殊情况要处理就是换的时候max在begin位置，因为先&arr[min], &arr[begin]换，所以要提前max=min.(此时最大值在min下标位置)

	if (max == begin) {	max = min;		}

时间复杂度n*(n/2+n/2)=n^2.

4堆排序

要了解堆排序我们要先了解一些误区：
1无论向下调整算案建堆还是向上调整算法建堆都是形成一个二叉树结构，本身并没有让数组完全有序，
2向下调整算法建堆比向上调整算法建堆时间复杂度更优
3排升序建大堆，排降序 建小堆。

所以我们要先完成堆排序的话要完成两个步骤，
1把原序列进行向下或向上调整遍历，成为一个堆的结构，
2因为头结点一定是最值，我们每次把arr[0]和arr[end]交换，再让end–完成之后就完成排序。

void HeapSort(HeapType* arr, int n) {//第一步for (int i = (n - 1 - 1) / 2; i >= 0; i--) {AdjustDown(arr, i, n);}int end = n - 1;for (int i = end; i > 0; i--) {//第二步Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}
}

因为向下调整算法建堆的时间复杂度大概是O（n）
第二部大概是O(nlogn)
故时间复杂度O（n+nlogn）大概是O（n*logn）.

三 交换排序

5冒泡排序

冒泡排序两层循环o(n^2)
加上优化还是最好情况O（n）所以是O（n^2）

void BubbleSort(int* a, int n) {for (int i = 0; i < n - 1; i++){int xz = 0;for (int j = 0; j < n - i - 1; j++) {if (a[j] > a[j + 1]) {swap(&a[j], &a[j + 1]);xz = 1;}}if (xz == 0) {break;}}}

6快速排序

快排我们用的找中间值 ，然后分区间，类似堆排序，时间复杂度o（nlogn）
按最情况来说，每次循环排最差情况是n/2+n/2=n,一共是logn次循环（最好情况，每次中间值恰好在中间）
按最坏情况是n次循环，所以时间复杂度为nlogn~n^2.

int GetKeyi(int* arr, int left, int right) {int keyi = left;left++;while (right>=left){while (left<=right&&arr[right]>arr[keyi]) {right--;}while (left <= right && arr[left] < arr[keyi]) {left++;}if (left <= right) {swap(&arr[right--], &arr[left++]);}}swap(&arr[keyi], &arr[right]);return right;
}
void QuickSort(int* arr, int left,int right) {if (left >= right) {return;}int keyi = GetKeyi(arr, left, right);QuickSort(arr, left,keyi - 1);QuickSort(arr, keyi+1,right);}

四 归并排序

7归并排序

归并排序的思想是通过二分找中间值，[left,中间值] ，[中间值+1,right]两个序列再二分，直到left>=中间值，然后通过递归返回原来的函数栈帧进行排序，因为只有logn个函数栈帧，每次栈帧内最坏排n个数据。

为了不破坏arr序列，我们定义了tem序列接收，然后最后把tem数组覆盖arr,
时间复杂度为n*logn

void MergeSort(int* arr, int n) {int* tem = (int*)malloc(sizeof(int) * n);_MergeSort(arr,0, n - 1,tem);free(tem);}
void _MergeSort(int* arr, int left, int right, int* tem) {if (left >= right) {return;}int mid = (left + right) / 2;_MergeSort(arr, left, mid, tem);_MergeSort(arr, mid+1, right, tem);int begin1 = left;int begin2 = mid + 1;int end1 = mid;int end2 = right;int x = begin1;while (begin1 <= end1 && begin2 <= end2) {if (arr[begin1] < arr[begin2]) {	tem[x++] = arr[begin1++];}else{tem[x++] = arr[begin2++];}}while (begin1 <= end1) {tem[x++] = arr[begin1++];}while (begin2 <= end2) {tem[x++] = arr[begin2++];}for (int i = left; i < right; i++){arr[i] = tem[i];}
}

最后总结一下所有排序时间

源码

Sort.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<assert.h>
#include<stdbool.h>
typedef int HeapType;
typedef struct Heap {HeapType* a;int capacity;int size;}Heap;
void SeletSort(HeapType* arr, int n);
void Inite(Heap* p);
void Push(Heap* p, HeapType x);
void Pop(Heap* p);
bool Empty(Heap* p);
HeapType Top(Heap* p);
void Print(Heap* p);
void Destry(Heap* p);
void Swap(HeapType* a, HeapType* b);
void AdjustUp(HeapType* a, int child);
void AdjustDown(HeapType* a, int parent, int n);
void HeapSort(HeapType* arr, int n);void BubbleSort(int* a, int n);
void swap(int* a, int* b);
void InsertSort(int* arr, int n);
void ShellSort(int* arr, int n);
int GetKeyi(int* arr, int left, int right);
void QuickSort(int* arr, int left, int right);
void MergeSort(int* arr,int n);
void _MergeSort(int* arr, int left, int right, int* tem);void test();

test.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"
#include"time.h"
#include"stdlib.h"int main() {test();return 0;
}

Sort.c

#define  _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"void test() {srand((unsigned)time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);//创建100000个空间的数组int* a2 = (int*)malloc(sizeof(int) * N);//创建100000个空间的数组int* a3 = (int*)malloc(sizeof(int) * N);//创建100000个空间的数组int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);int* a7 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; i++) {a1[i] = rand();//循环100000次，每次赋予a1数组随机值a2[i] = a1[i];//赋值值来自上次一数组a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];a7[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3= clock();SeletSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();BubbleSort(a5, N);int end5 = clock();int begin6= clock();QuickSort(a6, 0,N-1);int end6 = clock();int begin7 = clock();MergeSort(a7,  N - 1);int end7 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("BubbleSort:%d\n", end5 - begin5);printf("QuickSort:%d\n", end6 - begin6);printf("MergeSort:%d\n", end7 - begin7);}
void swap(int* a, int* b) {int tmp = *a;*a = *b;*b = tmp;}
void BubbleSort(int* a, int n) {for (int i = 0; i < n - 1; i++){int xz = 0;for (int j = 0; j < n - i - 1; j++) {if (a[j] > a[j + 1]) {swap(&a[j], &a[j + 1]);xz = 1;}}if (xz == 0) {break;}}}void InsertSort(int* arr, int n) {for (int i = 0; i < n - 1; i++) {int end = i;int tem = arr[end + 1];while (end >= 0) {if (arr[end] > tem) {arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tem;}}
void ShellSort(int* arr, int n) {int gap = n;while (gap > 1) {gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++) {int end = i;int tem = arr[end + gap];while (end >= 0) {if (arr[end] > tem) {arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tem;}}}
void SeletSort(int* arr, int n) {int end = n - 1;int begin = 0;int max, min;max = min = 0;while (begin < end) {max = min = begin;for (int i = begin + 1; i <= end; i++){if (arr[i] > arr[max]) {max = i;}if (arr[i] < arr[min]){min = i;}}if (max == begin) {max = min;}Swap(&arr[min], &arr[begin]);Swap(&arr[max], &arr[end]);begin++;end--;}}
void Inite(Heap* p) {p->a = NULL;p->capacity = p->size = 0;}
void Push(Heap* php, HeapType x)
{assert(php);if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HeapType* tmp = (HeapType*)realloc(php->a, newcapacity * sizeof(HeapType));if (tmp == NULL){perror("realloc fail");return;}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;php->size++;AdjustUp(php->a, php->size - 1);
}
void Pop(Heap* p) {Swap(&p->a[0], &p->a[p->size - 1]);p->size--;AdjustDown(p->a, 0, p->size);}
bool Empty(Heap* p) {return p->size == 0;}
HeapType Top(Heap* p) {return p->a[0];}
void Print(Heap* p) {{while (!Empty(p)){printf("%d ", Top(p));Pop(p);}}
}
void Swap(HeapType* a, HeapType* b) {int tem = *a;*a = *b;*b = tem;}
void AdjustUp(HeapType* a, int child) {int parent = (child - 1) / 2;while (child > 0) {if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void AdjustDown(HeapType* a, int parent, int n) {int child = parent * 2 + 1;while (child < n){if (child + 1 < n && a[child] > a[child + 1]) {child = child + 1;}if (a[parent] > a[child]) {Swap(&a[parent], &a[child]);parent = child;child = child * 2 + 1;}else{break;}}}
void HeapSort(HeapType* arr, int n) {for (int i = (n - 1 - 1) / 2; i >= 0; i--) {AdjustDown(arr, i, n);}int end = n - 1;for (int i = end; i > 0; i--) {Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}
}
int GetKeyi(int* arr, int left, int right) {int keyi = left;left++;while (right>=left){while (left<=right&&arr[right]>arr[keyi]) {right--;}while (left <= right && arr[left] < arr[keyi]) {left++;}if (left <= right) {swap(&arr[right--], &arr[left++]);}}swap(&arr[keyi], &arr[right]);return right;
}
void QuickSort(int* arr, int left,int right) {if (left >= right) {return;}int keyi = GetKeyi(arr, left, right);QuickSort(arr, left,keyi - 1);QuickSort(arr, keyi+1,right);}
void MergeSort(int* arr, int n) {int* tem = (int*)malloc(sizeof(int) * n);_MergeSort(arr,0, n - 1,tem);free(tem);}
void _MergeSort(int* arr, int left, int right, int* tem) {if (left >= right) {return;}int mid = (left + right) / 2;_MergeSort(arr, left, mid, tem);_MergeSort(arr, mid+1, right, tem);int begin1 = left;int begin2 = mid + 1;int end1 = mid;int end2 = right;int x = begin1;while (begin1 <= end1 && begin2 <= end2) {if (arr[begin1] < arr[begin2]) {	tem[x++] = arr[begin1++];}else{tem[x++] = arr[begin2++];}}while (begin1 <= end1) {tem[x++] = arr[begin1++];}while (begin2 <= end2) {tem[x++] = arr[begin2++];}for (int i = left; i < right; i++){arr[i] = tem[i];}
}