排序: 插入\希尔\选择\归并\冒泡\快速\堆排序实现

1.排序的概念及应用

1.1概念

排序:所谓排序，就是一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

1.2运用

购物筛选排序：

1.3常见排序算法 

2.实现常见的排序算法

int a[ = {5,3,9,6,2,4,7,1,8}; 

2.1插入排序

基本思想：直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其相关键码值逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。我们可以理解成玩扑克牌 

2.1.1直接插入排序

当插入第i个元素时，前面的arr[0],arr[1],arr[2].....,arr[i-1]已经排好序，此时用arr[i]的排序码与arr[i-1],arr[i-2]....的排序码顺序相比较，找到插入位置即将arr[i]插入，原来位置上的与元素挨个向后移动。 

代码实现:

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

直接插入排序的特性总结：

1.元素集合越接近有序，直接插入排序算法的效率越高

2.时间复杂度：O(N^2)

3.空间复杂度：O(1) 

2.1.2希尔排序

希尔排序的特性总结：

1.希尔排序是对直接插入排序的优化

2.当gap>1时都是预排序，目的时让数组更接近有序。当gap==1时，数组已经接近有序的了，这样就会很快。这样总体而言，可以达到优化的效果。 

代码实现:

/希尔排序
void shellSort(int* arr, int n)
{int gap = n;while (gap > 1){gap = gap / 3+1;//3 1 0 要保证最后一次为1for (int i = 0; i < n - gap; i++){int end = i;//n-gap-1int tmp = arr[end + gap];//n-1while (end>=0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}
}

 2.1.2.1希尔排序的时间复杂度计算

希尔排序的时间复杂度估算：

外层循环：外层循环的时间复杂度可以直接给出为：O(log2 n) 或者 O(log3 n) ，即 O(log n)

内层循环：

假设一共有n个数据，合计gap组，则每组为n/gap个数据；在每组中，插入移动的次数最坏的情况下为1+2+3+4+.....+(n/gap-1),一共是gap组，因此：

总计最坏情况下移动总数为：gap*[1+2+3+...+n/gap-1]

gap取值有（以除3为例）：n/3 n/9 n/27.....2 1

2.2选择排序

选择排序的基本思想：每一次从待排序的数据元素中选出最小或者最大的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

2.2.1直接选择排序

1.在元素集合arr[i]--arr[n-1]中选择最大和最小的数据元素

2.若它不是这个组元素中的最后一个元素或者第一个元素，则将它与这组元素中的最后一个和第一个元素进行交换

3.在剩余的arr[i]--arr[n-1]  arr[i+1]--arr[n-2]集合中，重复上面的步骤直到集合只剩一个元素

//选择排序
void SelectSort(int* arr, int n)
{int begin = 0;int end = n - 1;while (begin<end){int mini = begin;int maxi = begin;for (int i = begin; i <= end; i++){if (arr[i] > arr[maxi]){maxi = i;}if (arr[i] < arr[mini]){mini = i;}}if (maxi == begin){maxi = mini;}Swap(&arr[begin], &arr[mini]);Swap(&arr[end], &arr[maxi]);begin++;end--;}}

直接选择排序非常好理解，但是效率不高，实际中很少用

时间复杂度:O(N^2)

空间复杂度:O(1) 

2.2堆排序

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}// 堆排序
void AdjustDwon(int* arr, int parent, int n)
{int child = 2 * parent + 1;//左孩子//大堆找最大//小堆找最小while (child < n){if (child + 1 < n && arr[child] < arr[child + 1]){child++;}if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = 2 * parent + 1;}else{break;}}
}void HeapSort(int* arr, int n)
{//1.先建堆//升序建大堆//降序建小堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDwon(arr, i, n);}//交换根结点和最后一个有效数据的位置（没交换一次少一个数据）然后向下调整int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);//向下调整AdjustDwon(arr, 0, end);end--;}
}

2.3交换排序 

交换排序基本思想：

2.3.1冒泡排序 

前⾯在算法题中我们已经接触过冒泡排序的思路了，冒泡排序是⼀种最基础的交换排序之所以叫做冒泡排序，因为每⼀个元素都可以像⼩⽓泡⼀样，根据⾃⾝⼤⼩⼀点⼀点向数组的⼀侧移动。

//冒泡排序
//时间复杂度：0(N^2)
void BubbleSort(int* arr, int n)
{for (int i = 0; i < n; i++){int exchange = 0;for (int j = 0; j < n - i - 1; j++){//升序if (arr[j] < arr[j + 1]){exchange = 1;Swap(&arr[j], &arr[j + 1]);}}if (exchange == 0){break;}}
}

冒泡排序的特性总结：

时间复杂度为：O(N^2)

空间复杂度为：O(1) 

2.3.2快速排序

快速排序是一种高效的排序算法，由英国计算机科学家托尼·霍尔（Tony Hoare）在1960年提出。它的基本思想是分而治之，通过一趟排序将待排记录分割成独立的两部分，其中一部分的所有记录均比另一部分的所有记录要小，然后再按此方法对这两部分分别进行快速排序，整个排序过程可以递归进行，以至整个数据变成有序序列。

快速排序实现的主框架：

//快速排序
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//找基准值midint key = _QuickSort(arr, left, right);//左子序列：[left,mid-1]QuickSort(arr, left, key - 1);//右子序列:[mid+1,right]QuickSort(arr, key + 1, right);
}

将区间中的元素划分的 _QuickSort方法主要有一下几种实现方式:

2.3.2.1hoare版本

算法思路：

1.创建左右指针，确定基准值

2.从右向左找比基准值小的数据，从左向右找比基准值大的数据，左右指针数据交换，进入下次循环。当left>right时，即right走到left的左侧，而left扫描过的数据均不大于key，因此right此时指向的数据一定不大于key。

left和right指向的数据与key相等时也要交换，相等的值参与交换确实有一些损耗。实际还有各种复杂的场景，假设数组中的数据大量重复时，无法进行有效的数据分割。 

代码实现：

//hoare法
int _QuickSort(int* arr, int left, int right)
{int key = left;left++;while (left<=right)//使效率更高{//right从右到左找比基准值小的while (left<=right&&arr[right]>arr[key]){right--;}//left从左到右找比基准值大的while (left<=right&&arr[left]<arr[key]){left++;}if (left <= right){Swap(&arr[left++], &arr[right--]);}}//跳出循环，交换right和基准值Swap(&arr[key], &arr[right]);//返回基准值return right;
}

2.3.2.2挖坑法

//挖坑法
int _QuickSort1(int* arr, int left, int right)
{int mid = arr[left];int hole = left;int key = arr[hole];while (left<right){while (left < right && arr[right] > key){right--;}//填坑arr[hole] = arr[right];hole = right;while (left<right&&arr[left]<key){left++;}//填坑arr[hole] = arr[left];hole = left;}arr[hole] = key;//返回基准值return hole;
}

//lomuto法
int _QuickSort2(int* arr, int left, int right)
{int prev = left;int cur = left + 1;int key = left;while (cur<=right){if (arr[cur] < arr[key] && ++prev != cur){Swap(&arr[cur], &arr[prev]);}cur++;}Swap(&arr[key], &arr[prev]);//返回基准值return prev;
}

快速排序的特性：

时间复杂度：O(n*logn)

空间复杂度：O(logn)

2.3.2.4非递归版本

非递归版本的快速排序需要借助数据结构：栈

//非递归
//栈结构
void QuickSortNonR(int* arr, int left, int right)
{ST st;STInite(&st);//入栈STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)) {//取栈顶--取两次int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);//找基准值int prev = begin;int cur = begin + 1;int key = begin;while (cur<=end){if (arr[cur] < arr[key] && ++prev != cur){Swap(&arr[prev], &arr[cur]);}cur++;}Swap(&arr[prev], &arr[key]);key = prev;//根据基准值划分左右区间//left:[begin,key-1]//right:[key+1,end]if (key+1<end){STPush(&st, end);STPush(&st, key + 1);}if (begin<key-1){STPush(&st, key - 1);STPush(&st, begin);}}STDestroy(&st);
}

2.4归并排序 

 归并排序算法思想：归并排序（MERGE-SORT是建⽴在归并操作上的⼀种有效的排序算法,算法是采⽤分治法（Divide and Conquer的⼀个⾮常典型的应⽤。将已有序的⼦序列合并，得到完全有序的序列；即先使每个 ⼦序列有序，再使⼦序列段间有序若将两个有序表合并成⼀个有序表称为⼆路归并。归并排序核⼼步骤：

void _mergeSort(int* arr, int left, int right,int* tmp)
{if (left >= right){return;}int mid = (left + right) / 2;//[left,mid]  [mid+1,right]_mergeSort(arr, left, mid, tmp);_mergeSort(arr, mid + 1, right, tmp);//合并//[left,mid]  [mid+1,right]int begin1 = left;int end1 = mid;int begin2 = mid + 1;int end2 = right;int index = begin1;while (begin1<=end1&&begin2<=end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else{tmp[index++] = arr[begin2++];}}//要么begin1越界，要么begin2越界while (begin1<=end1){tmp[index++] = arr[begin1++];}while (begin2<=end2){tmp[index++] = arr[begin2++];}//把tmp中的数据拷贝会arr中for (int i = left; i <=right; i++){arr[i] = tmp[i];}
}
//归并排序
void mergeSort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_mergeSort(arr, 0, n - 1, tmp);free(tmp);
}

归并排序特性总结：

时间复杂度：O(n*logn)

空间复杂度： O(n)

2.5计数排序

//计数排序
void CountSort(int* arr, int n)
{int max = arr[0];int min = arr[0];//找到最大值和最小值求范围for (int i = 1; i < n; i++){if (arr[i] < min){min = arr[i];}if (arr[i] > max){max = arr[i];}}int range = max - min + 1;//开辟数组大小int* count = (int*)malloc(sizeof(int) * range);if (count == NULL){perror("malloc fail!");exit(1);}//初始化置为0memset(count, 0, range * sizeof(int));//统计数组中每个数据出现的次数for (int i = 0; i < n; i++){count[arr[i] - min]++;}//取count中的数据往arr中放int index = 0;for (int i = 0; i < range; i++){while (count[i]--){arr[index++] = i + min;}}
}

2.6测试代码：排序性能对比

//测试排序性能
void Testop()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);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);int* a8 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];a7[i] = a1[i];a8[i] = a1[i];}int begin7 = clock();BubbleSort(a7, N);int end7 = clock();int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();shellSort(a2, N);int end2 = clock();int begin3 = clock();SelectSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();QuickSort(a5, 0, N - 1);//QuickSortNonR(a5, 0, N - 1);int end5 = clock();int begin6 = clock();mergeSort(a6, N);int end6 = clock();int begin8 = clock();CountSort(a8, N);int end8 = 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("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);printf("BubbleSort:%d\n", end7 - begin7);printf("CountSort:%d\n", end8 - begin8);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);free(a8);
}