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

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希尔排序

希尔排序法⼜称缩⼩增量法。希尔排序法的基本思想是：先选定⼀个整数（通常是gap =n/3+1），把 待排序⽂件所有记录分成各组，所有的距离相等的记录分在同⼀组内，并对每⼀组内的记录进⾏排 序，然后gap=gap/3+1得到下⼀个整数，再将数组分成各组，进⾏插⼊排序，当gap=1时，就相当于 直接插⼊排序。它是在直接插⼊排序算法的基础上进⾏改进⽽来的，综合来说它的效率肯定是要⾼于直接插⼊排序算 法的。

 

希尔排序的特性总结：

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

• 当gap为n/3时，移动总数为：n/3  ∗   (1 + 2) = n

• 当gap为n/9时，移动总数为： n/9  ∗  (1 + 2 + 3 + .... + 8) = n/9∗  8(1 + 8)/2 =4n

• 最后⼀躺，gap=1即直接插⼊排序，内层循环排序消耗为n

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堆排序

堆排序(Heapsort)是指利⽤堆积树（堆）这种数据结构所设计的⼀种排序算法，它是选择排序的⼀

种。它是通过堆来进⾏选择数据。需要注意的是排升序要建⼤堆，排降序建⼩堆。

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

2.3.2.3lomuto前后指针

创建前后指针，从左往右找比基准值小的进行交换，使得小的都排在基准值的左边。

//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计数排序

计数排序⼜称为鸽巢原理，是对哈希直接定址法的变形应⽤。 操作步骤：

1）统计相同元素出现次数

2）根据统计的结果将序列回收到原来的序列中

//计数排序
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);
}