码海拾遗：常用的其中排序算法

排序算法大致可分为两类：

　　比较排序，时间复杂度一般在O(nlogn) ~ O(n^2)之间，主要有冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、堆排序等

　　非比较排序，时间复杂度可达到O(n)，主要有计数排序、基数排序等

本文主要介绍常用的其中比较排序。

　　 1、冒泡排序

　　说明：冒泡排序是一种非常简单的排序算法，需要重复遍历需要排序的所有元素，依次比较相邻的两个元素，如果顺序错误就将两者位置调换，知道没有元素需要交换位置，排序结束。

　　平均时间复杂度：O(n^2)。

　　稳定性：稳定。

　　2、选择排序

　　说明：开始时找到序列中的最小（大）元素，放到序列的起始位置作为已排序序列，然后再从剩余未排序序列中找的最小（大）的元素，放到已排序序列的末尾；以此类推，直至所有元素都排序完成。

　　平均时间复杂度：O(n^2)。

　　稳定性：不稳定。

　　3、插入排序

　　说明：将未排序的元素在已排序的序列中从后向前找到相应的位置插入。

　　平均时间复杂度：O(n^2)。

　　稳定性：稳定

　　4、希尔排序

　　说明：又称递减增量排序，是插入排序的一种高速改进版本。

　　平均时间复杂度：希尔排序的时间复杂度与增量的选取有关，当增量为1时，为O(n^2)，Hibbard增量的希尔排序的时间复杂度为O(N^3/2)。

　　稳定性：不稳定

　　5、快速排序

　　说明：使用分而治之的策略把一个序列分成两个子序列

　　平均时间复杂度：O(nlogn)

　　稳定性：不稳定

　　6、归并排序

　　说明：建立在归并操作上的一种排序算法，由冯·诺依曼首次提出。

　　平均时间复杂度：O(nlogn)

　　稳定性：稳定

　　7、堆排序

　　说明：利用堆这种数据结构设计的排序算法，堆是一种近似完全二叉树的结构，并满足性质：以大顶堆为例，父节点的元素总大于子节点的元素。

　　平均时间复杂度：O(nlogn)

　　稳定性：不稳定

　　实现：my_sort.h

 1 #pragma once
 2 
 3 //两值交换
 4 void swap(int& a, int& b);
 5 void swap(int arr[],int i,int j);
 6 
 7 //选择排序
 8 void selectSort(int arr[], int arrSize);
 9 
10 //插入排序
11 void insertSort(int arr[], int arrSize);
12 
13 //冒泡排序
14 void bubbleSort(int arr[], int arrSize);
15 
16 //希尔排序
17 void shellSort(int arr[], int arrSize);
18 
19 //快速排序
20 void quickSort(int arr[],int start,int end);
21 
22 //归并排序
23 void mergeSort(int a[], int first, int last, int temp[]);
24 //将两个有序数列a[first...mid]和a[mid+1...last]合并。
25 void mergeArray(int a[], int first, int mid, int last, int temp[]);
26 
27 //堆排序
28 void heapSort(int arr[], int arrSize);
29 //建堆
30 int buildHeap(int arr[], int arrSize);
31 //从指定节点开始向下进行堆调整
32 void heap(int arr[], int i, int size);

my_sort.cpp

  1 #include "my_sort.h"
  2 
  3 void swap(int & a, int & b)
  4 {
  5     int tmp = a;
  6     a = b;
  7     b = tmp;
  8 }
  9 
 10 void swap(int arr[], int i, int j)
 11 {
 12     int tmp = arr[i];
 13     arr[i] = arr[j];
 14     arr[j] = tmp;
 15 }
 16 
 17 //选择排序
 18 void selectSort(int arr[], int arrSize)
 19 {
 20     int min = 0;//初始时最小值位置
 21     for (int i = 0; i < arrSize - 1; ++i)
 22     {
 23         min = i;
 24         for (int j = i + 1; j < arrSize; ++j)
 25             if (arr[min] > arr[j])
 26                 min = j;
 27 
 28         if (min != i)
 29             swap(arr[min], arr[i]);
 30     }
 31 }
 32 
 33 //插入排序
 34 void insertSort(int arr[], int arrSize)
 35 {
 36     int i, j;
 37     for (i = 1; i < arrSize; ++i)
 38     {
 39         int tmp = arr[i];
 40         for (j = i; j > 0 && tmp<arr[j-1]; --j)
 41         {
 42             arr[j] = arr[j - 1];
 43         }
 44         arr[j] = tmp;
 45     }
 46 }
 47 
 48 //冒泡排序
 49 void bubbleSort(int arr[], int arrSize)
 50 {
 51     for (int i = 0; i < arrSize; ++i)
 52     {
 53         for (int j = 1; j < arrSize - i; ++j)
 54         {
 55             if (arr[j] < arr[j - 1])
 56                 swap(arr[j], arr[j - 1]);
 57         }
 58     }
 59 }
 60 
 61 //希尔排序
 62 void shellSort(int arr[], int arrSize)
 63 {
 64     int step = arrSize / 2;//设置步长
 65     int i, j;
 66     int tmp;
 67     while (step >= 1)
 68     {
 69         for (i = step; i < arrSize; ++i)
 70         {
 71             tmp = arr[i];
 72             j = i - step;
 73             while (j > 0 && arr[j] > tmp)
 74             {
 75                 arr[j + step] = arr[j];
 76                 j -= step;
 77             }
 78             arr[j + step] = tmp;
 79         }
 80         step /= 2;
 81     }
 82 }
 83 
 84 //快速排序
 85 void quickSort(int arr[], int start, int end)
 86 {
 87     if (start >= end)
 88         return;
 89 
 90     int i = start;//起始位置
 91     int j = end;//最后一个元素的位置
 92 
 93     //基准值
 94     int tmp = arr[start];//以起始位置为基准
 95 
 96     while (i < j)
 97     {
 98         while (i < j&&arr[j] >= tmp)
 99             j--;
100         if (i < j)
101         {
102             arr[i] = arr[j];
103             i++;
104         }
105 
106         while (i < j&&arr[i] < tmp)
107             i++;
108         if (i < j)
109         {
110             arr[j] = arr[i];
111             j--;
112         }
113     }
114 
115     arr[i] = tmp;
116 
117     quickSort(arr, start, i - 1);
118     quickSort(arr, i + 1, end);
119 
120 }
121 
122 //将两个有序数列a[first...mid]和a[mid+1...last]合并。
123 void mergeArray(int a[], int first, int mid, int last, int temp[])
124 {
125     int i = first;    // 第一个有序序列的开始下标
126     int j = mid + 1;    // 第2个有序序列的开始下标
127 
128     int length = 0;
129     // 合并两个有序序列
130     while (i <= mid && j <= last)
131     {
132         // 找二者中比较小的数
133         if (a[i] < a[j])
134         {
135             temp[length] = a[i];
136             i++;
137         }
138         else
139         {
140             temp[length] = a[j];
141             j++;
142         }
143         length++;
144     }
145     // 还剩下一个有序序列中有数据
146     while (i <= mid)
147     {
148         temp[length] = a[i];
149         i++;
150         length++;
151     }
152     while (j <= last)
153     {
154         temp[length++] = a[j++];
155     }
156 
157     // 覆盖原来位置的无序序列
158     for (int i = 0; i < length; ++i)
159     {
160         // 找到原来 的第一个有序序列的开始位置 - 开始覆盖
161         a[first + i] = temp[i];
162     }
163 }
164 //归并排序
165 void mergeSort(int a[], int first, int last, int temp[])
166 {
167     // 递归结束的条件
168     if (first == last)
169     {
170         return;
171     }
172     // 从中间位置拆分
173     int mid = (first + last) / 2;
174     // 拆分
175     // 左半边
176     mergeSort(a, first, mid, temp);
177     // 右半边
178     mergeSort(a, mid + 1, last, temp);
179     // 合并两个有序序列
180     mergeArray(a, first, mid, last, temp);
181 }
182 
183 //堆排序
184 void heapSort(int arr[], int arrSize)
185 {
186     int heapSize = buildHeap(arr, arrSize);
187     while (heapSize > 1)
188     {
189         swap(arr, 0, --heapSize);
190         heap(arr, 0, heapSize);
191     }
192 
193 }
194 //建堆
195 int buildHeap(int arr[], int arrSize)
196 {
197     int heapSize = arrSize;
198     for (int i = heapSize / 2 - 1; i >= 0; i--)
199         heap(arr, i, heapSize);
200     return heapSize;
201 }
202 //从指定节点开始向下进行堆调整
203 void heap(int arr[], int i, int size)
204 {
205     int leftChild = 2 * i + 1;
206     int rightChild = 2 * i + 1;
207     int max = i;
208 
209     if (leftChild<size&&arr[leftChild]>arr[max])
210         max = leftChild;
211     if (rightChild<size&&arr[rightChild]>arr[max])
212         max = rightChild;
213     if (max != i)
214     {
215         swap(arr, i, max);
216         heap(arr, max, size);
217     }
218 }

　　排序算法的稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，则称这种排序算法是稳定的；否则称为不稳定的。

　　源码地址：https://github.com/MasterMeng/sort