排序算法综合实例 - 好文

插入排序

* 思想：从数组第二个元素开始，每次选取一个作为待排元素，与已排好的元素依次比较。
* 如果待排元素比已排元素小，则已排元素依次后移。最后把待排元素插入到合适的位置。
* 插入排序的平均复杂度为O(n2)O(n2)。
插入排序函数模板
template<typename T> void InsertSort(T* list, int n) // 选择排序函数的实现 { T temp; //
定义一个临时T类型变量 for (int i = 1;i < n;i++) { temp = list[i]; // 临时变量赋值为下一个要排序的新元素 int
j = i-1; // 令下标j为i-1，前i-1个元素已经排好序 while (temp < list[j]) // 比较新元素与前i-1个元素大小 {
list[j + 1] = list[j]; // 若新元素值小于前面排好序的数，前面的数依次后移 j--; // j前移 } list[j + 1] =
temp; } }
冒泡排序

* 思想：每一趟从头到尾，一次比较相邻两个元素，上面（前面）比下面（后面）大，则交换两个元素的位置。
* 每一趟将较大的值“下沉”，较小的值“冒泡上升”，最终固定较大值的位置。总共有n-1趟冒泡排序。
* 冒泡排序的平均复杂度为O(n2)O(n2)。
冒泡排序函数模板
template<typename T> void BubbleSort(T* list, int n) // 冒泡排序函数的实现 { for (int i
=0;i < n - 1;i++) // 总共有n-1趟 { for (int j = 1;j < n - i;j++) // 遍历数组 { if (list
[j -1] > list[j]) // 依次比较相邻两个数的值，较大数下沉，较小的数上冒 mySwap(list[j - 1], list[j]); } }
}
选择排序

* 思想：每次从未排序的元素中挑选一个最小值与前面待排位置的元素交换。
* 选择排序的平均时间复杂度为O(n2)O(n2)。
选择排序函数模板
template<typename T> void SelectSort(T *a, int n) // 选择排序函数模板 { for (int i = 0
;i < n;i++)// 总共有size趟 { int minIndex = i; // 每趟从剩下的元素中寻找最小的元素，初始化第i趟最小元素下标为i
for (int j = i + 1;j < n;j++) { if (a[j] < a[minIndex]) minIndex = j; //
更新最小元素下标 } mySwap(a[i], a[minIndex]); // 交换第i个元素与第i趟最小元素的位置 } }
希尔排序（增量排序）

* 每次将一定间隔（增量）位置上的元素（看作子数组）在相应位置上进行插入排序。增量依次减小。
* 当增量为1时，数组基本有序，再进行一次直接插入排序完成整个排序过程。
* 希尔排序的最坏时间复杂度为O(n2)O(n2)，使用Hibbard增量的希尔排序最坏时间为O(n3/2)O(n3/2)。
* Sedgewick提出的几种增量序列，最坏时间为O(n4/3)O(n4/3)，平均时间猜测为O(n7/6)O(n7/6)。
* 希尔排序适用于大量输入数据的排序，在实际运行时比堆排序快。
希尔排序函数模板
template<typename T> void ShellSort(T* list, int n) { int increment = n / 2;
// 定义初始增量为size/2 T temp; // 临时T类型变量 while (increment > 0) // 增量大于0时执行循环 { for (
int i = increment;i < n;i++) { temp = list[i]; int j = i - increment; //
j为前面已排好的一定间隔的数组 while (temp < list[j] && j >= 0) // 临时变量小于前面排好的元素，则已排好元素依次后移 {
list[j + increment] = list[j]; j -= increment; // j按增量前移 } list[j + increment]
= temp; } increment /=2; // 增量变为原来的一半 } }
堆排序

* 首先从待排数组中构建一个大堆，交换堆顶元素与数组（堆）末尾元素（即最大的数移到数组最末尾）。
* 然后，将新的堆顶元素执行下滤操作，构建一个包含前n-1项元素的新大堆，再交换堆顶与堆末尾元素。
* 如此反复进行n-1次，最终实现从小到大的排序。
* 堆排序理论平均和最坏时间复杂度都为O(NlogN)O(Nlog⁡N)。但在实践中比希尔排序慢。
堆排序函数模板
template<typename T> void HeapDown(T* list, int i, int N) //
构建（大顶）堆的辅助函数，"下滤"地调整堆 { T temp = list[i]; // 临时变量保存节点i的值，将节点i看作为"空穴" int
BigChild;// 这里创建一个"大孩子"表示数值较大的孩子 while (2*i + 1 < N) //
当i("空穴")左孩子的下标小于数组（堆）大小时执行"下滤"操作 { if (2*i + 2 >= N) // 当i("空穴")右孩子(2*i + 2 >=
N)，右孩子不存在，"大孩子"直接为其左孩子（根据堆为完全二叉树这里只可能是左孩子） BigChild = 2 * i + 1; else //
否则i("空穴")有左(2 * i + 1)右(2 * i + 2)两个孩子 BigChild = list[2 * i + 1] > list[2 * i +
2] ? 2 * i + 1 : 2 * i + 2; // "大孩子"为值比较大的孩子 if (list[BigChild] > temp) //
如果"大孩子"的值大于临时变量 { list[i] = list[BigChild]; // 填充i("空穴")为其大孩子的值 i = BigChild;
// 更新i的值("空穴"下移)，赋值为其大孩子 } else break; // 否则，i("空穴")的孩子没有比它大的，则"空穴"停止移动 } list
[i] = temp;// 在相应的"空穴"位置，填充最初的节点i的值 } template<class T> void HeapSort(T* list,
int n) // 堆排序函数 { // 从数组中构建堆 for (int i = n / 2 - 1; i >= 0;i--) { HeapDown(list
, i, n);// 从最末尾的非树叶节点(size/2)开始执行"下滤"调整操作，直至调整至根节点，创建了一个大堆 } //
从构建好的队里，执行"DeleteMax"操作 for (int i = n - 1;i > 0;i--) { mySwap(list[0], list
[i]);// 将堆顶元素（数组最大值）与堆尾元素交换位置 HeapDown(list, 0, i); //
"下滤"调整除去最大值的堆结构（只有根节点改变，故只需调整元素下标为0的"非页节点"），以便后续操作 } }
归并排序

* 典型利用分治递归策略的例子。首先，考虑两个有序的子数组，很容易将它们合并成一个有序的子数组。
*
合并操作：每次选取两个子数组中的较小的数到合并数组中，被选取的子数组下标后移，直到一个子数组被选完，另一个子数组剩下的元素依次移动到合并数组的末尾。整个合并数组有序排列。
*
分治递归：将整个数组划分为两路，两路划分为四路……直到每路都只包含一个元素（一个元素本身就有序）。然后依次从低向上进行合并，每次合并之后的子数组也有序，最终合并到一个有序的数组。
* 归并排序的最坏时间复杂度为O(NlogN)O(Nlog⁡N)。
*
合并操作函数模板
template<typename T> void Merge(T* A, int p, int q, int r) //
归并排序辅助函数，用于对左右有序的数组进行合并 { T *templist = new T[12]; int i = p, j = p, k = q + 1;
// i为临时数组的下标，j为左部分起始下标，k为右半部分起始下标 while (j <= q && k <= r) // 左右两部分下标分别再其范围内时 {
if (A[j] < A[k]) // 比较左右两部分的元素，当左部分元素小于右部分元素时 { templist[i++] = A[j]; // 赋值给临时数组
j++;// 下标后移 } else { templist[i++] = A[k]; k++; } } while (j <= q) //
左半部分剩余元素依次复制到临时数组中 { templist[i++] = A[j]; j++; } while (k <= r) // 若右边有剩余元素 {
templist[i++] = A[k];// 依次把剩余元素填到templist后面 k++; } for (i = p;i <= r;i++) {
A[i] = templist[i];// 临时数组中的元素依次赋值到A中 } }
合并排序驱动函数模板
template<typename T> void MergeSort(T* list, int p, int r) // 合并排序函数模板实现 { if
(p < r) {int mid = (p + r) / 2; // 中点q MergeSort(list, p, mid); // 递归地归并排序左半部分
MergeSort(list, mid + 1, r); // 递归地归并排序右半部分 Merge(list, p, mid, r); //
递归地左右两部分合并 } }
快速排序

* 同样采用分治递归的策略。首先从数组中选取一个数作为“枢纽元”。
* 分别从后往前、从前往后遍历数组，依次将从后往前的比“枢纽元”大的元素与从前往后的比“枢纽元”小的元素调换位置。
* 当前后遍历的下标有交叉时停止遍历，在相应位置填充“枢纽元”。此时，数组中在“枢纽元”之前的都比它小，之后的元素都比它大。完成了一次快速排序。
* 以“枢纽元”为界划分前后两个子数组，递归地在子数组中进行快速排序。递归终止的条件为某子数组“开始”位置不小于“终止”位置。
* 快速排序的平均时间复杂度为O(NlogN)O(Nlog⁡N)，最坏为O(N2)O(N2)，但在实践中，快速排序时目前已知的最快的排序算法。
快速排序函数模板
template<typename T> void QuickSort(T* A, int start, int end) // 快速排序函数模板 { int
i = start +1, j = end; // 以开头为"枢纽元" while (i < j) { while (A[j] > A[start]) //
从后往前，寻找一个比"枢纽元"小的数 j--; while (A[i] < A[start]) // 从前往后，寻找一个比"枢纽元"大的数 i++; if(i
< j) mySwap(A[i], A[j]);// 交换两个数的位置 } mySwap(A[start], A[j]); //
交换"枢纽元"与最后一个比它小的值的位置 if (--j > start) QuickSort(A, start, j); //
递归地对前面都比"枢纽元"小的元素进行快速排序 if (i < end) QuickSort(A, i, end); //
递归地对前面都比"枢纽元"大的元素进行快速排序 }
附排序综合实例（基于数组类模板）C/C++
#include<iostream> #include<cassert> using namespace std; template<typename T>
// 数组类模板定义 class Array { // 创建一个静态数组类 public: Array(int sz); // 构造函数 Array(const
Array<T> &a);// 复制构造函数 ~Array(); // 析构函数 int getSize(); // 返回数组大小 Array<T>&
operator = (const Array<T> &rhs); // 重载"="运算符 T & operator [] (int i); //
重载"[]"下标操作符 const T & operator [] (int i) const; // 重载"[]"常函数 operator T*(); //
重载到T*类型的转换 void insertSort(); // 插入排序 void bubbleSort(); // 冒泡排序 void
selectSort();// 选择排序 void shellSort(); // 希尔排序 void heapSort(); // 堆排序 void
mergeSort();// 归并排序 void quickSort(); // 快速排序 template<typename T> //
友元函数的声明，前面要加上类模板声明 friend void print(Array<T> a); // 打印数组 private: T* list; //
数组元素的头指针 int size; // 数组大小 }; // 实现类 template<typename T> Array<T>::Array(int
sz)// 构造函数的实现 { assert(sz >= 0); size = sz; list = new T[size]; //
动态分配size个T类型的元素空间 } template<typename T> Array<T>::Array(const Array<T> &a) //
复制构造函数的实现 { this->size = a.size; // 数组大小不变 this->list = new T [size]; //
动态分配size个T类型的新空间 for (int i = 0;i < size;i++) // 深层复制构造 { this->list[i] = a.list
[i]; } }template<typename T> Array<T>::~Array() // 析构函数 { delete[] list; }
template<typename T> int Array<T>::getSize() { return size; } template<typename
T> T & Array<T>::operator [] (int i) // 重载"[]"下标操作符 { assert(i >= 0 && i <
size);return list[i]; } template<typename T> const T & Array<T>:: operator [] (
int i) const // 重载"[]"常函数 { assert(i >= 0 && i < size); return list[i]; }
template<typename T> Array<T>& Array<T>::operator = (const Array<T> &rhs) //
重载"="运算符 { if (&rhs != this) { if (size != rhs.size) { delete[] list; //
删除数组原有内存 size = rhs.size; // 动态分配新内存 list = new T[size]; } } for (int i = 0;i <
size;i++) {list[i] = rhs.list[i]; } } template<typename T> Array<T>::operator
T*()// 重载到T*类型的转换 { return list; } template<typename T> void InsertSort(T* list,
int n) // 选择排序函数的实现 { T temp; // 定义一个临时T类型变量 for (int i = 1;i < n;i++) { temp =
list[i]; // 临时变量赋值为下一个要排序的新元素 int j = i-1; // 令下标j为i-1，前i-1个元素已经排好序 while (temp
<list[j]) // 比较新元素与前i-1个元素大小 { list[j + 1] = list[j]; // 若新元素值小于前面排好序的数，前面的数依次后移
j--;// j前移 } list[j + 1] = temp; } } template<typename T> void
Array<T>::insertSort()// 类成员选择排序函数的实现 { InsertSort(list, size); } template<
typename T> // 创建两个数的交换函数模板 void mySwap(T &a, T &b) { T temp = a; a = b; b =
temp; }template<typename T> void BubbleSort(T* list, int n) // 冒泡排序函数的实现 { for (
int i = 0;i < n - 1;i++) // 总共有n-1趟 { for (int j = 1;j < n - i;j++) // 遍历数组 { if
(list[j - 1] > list[j]) // 依次比较相邻两个数的值，较大数下沉，较小的数上冒 mySwap(list[j - 1], list
[j]); } } }template<typename T> void Array<T>::bubbleSort() // 冒泡排序函数的实现 {
BubbleSort(list, size); } template<typename T> void SelectSort(T *a, int n) //
选择排序函数模板 { for (int i = 0;i < n;i++) // 总共有size趟 { int minIndex = i; //
每趟从剩下的元素中寻找最小的元素，初始化第i趟最小元素下标为i for (int j = i + 1;j < n;j++) { if (a[j] <
a[minIndex]) minIndex = j;// 更新最小元素下标 } mySwap(a[i], a[minIndex]); //
交换第i个元素与第i趟最小元素的位置 } } template<typename T> void Array<T>::selectSort() //
选择排序函数的类成员实现 { SelectSort(list, size); } template<typename T> void ShellSort(T*
list, int n) { int increment = n / 2; // 定义初始增量为size/2 T temp; // 临时T类型变量 while
(increment >0) // 增量大于0时执行循环 { for (int i = increment;i < n;i++) { temp = list
[i];int j = i - increment; // j为前面已排好的一定间隔的数组 while (temp < list[j] && j >= 0)
// 临时变量小于前面排好的元素，则已排好元素依次后移 { list[j + increment] = list[j]; j -= increment; //
j按增量前移 } list[j + increment] = temp; } increment /= 2; // 增量变为原来的一半 } } template
<typename T> void Array<T>::shellSort() { ShellSort(list, size); } template<
typename T> void HeapDown(T* list, int i, int N) // 构建（大顶）堆的辅助函数，"下滤"地调整堆 { T
temp =list[i]; // 临时变量保存节点i的值，将节点i看作为"空穴" int BigChild; // 这里创建一个"大孩子"表示数值较大的孩子
while (2*i + 1 < N) // 当i("空穴")左孩子的下标小于数组（堆）大小时执行"下滤"操作 { if (2*i + 2 >= N) //
当i("空穴")右孩子(2*i + 2 >= N)，右孩子不存在，"大孩子"直接为其左孩子（根据堆为完全二叉树这里只可能是左孩子） BigChild = 2
* i +1; else // 否则i("空穴")有左(2 * i + 1)右(2 * i + 2)两个孩子 BigChild = list[2 * i + 1
] >list[2 * i + 2] ? 2 * i + 1 : 2 * i + 2; // "大孩子"为值比较大的孩子 if (list[BigChild]
> temp)// 如果"大孩子"的值大于临时变量 { list[i] = list[BigChild]; // 填充i("空穴")为其大孩子的值 i =
BigChild;// 更新i的值("空穴"下移)，赋值为其大孩子 } else break; // 否则，i("空穴")的孩子没有比它大的，则"空穴"停止移动
}list[i] = temp; // 在相应的"空穴"位置，填充最初的节点i的值 } template<class T> void HeapSort(T*
list, int n) // 堆排序函数 { // 从数组中构建堆 for (int i = n / 2 - 1; i >= 0;i--) {
HeapDown(list, i, n); // 从最末尾的非树叶节点(size/2)开始执行"下滤"调整操作，直至调整至根节点，创建了一个大堆 } //
从构建好的队里，执行"DeleteMax"操作 for (int i = n - 1;i > 0;i--) { mySwap(list[0], list
[i]);// 将堆顶元素（数组最大值）与堆尾元素交换位置 HeapDown(list, 0, i); //
"下滤"调整除去最大值的堆结构（只有根节点改变，故只需调整元素下标为0的"非页节点"），以便后续操作 } } template<class T> void
Array<T>::heapSort()// 堆排序函数 { HeapSort(list, size); } template<typename T> void
Merge(T* A,int p, int q, int r) // 归并排序辅助函数，用于对左右有序的数组进行合并 { T *templist = new
T[12]; int i = p, j = p, k = q + 1; // i为临时数组的下标，j为左部分起始下标，k为右半部分起始下标 while (j
<= q && k <= r)// 左右两部分下标分别再其范围内时 { if (A[j] < A[k]) //
比较左右两部分的元素，当左部分元素小于右部分元素时 { templist[i++] = A[j]; // 赋值给临时数组 j++; // 下标后移 } else
{ templist[i++] = A[k]; k++; } }while (j <= q) // 左半部分剩余元素依次复制到临时数组中 {
templist[i++] = A[j]; j++; }while (k <= r) // 若右边有剩余元素 { templist[i++] = A[k];
// 依次把剩余元素填到templist后面 k++; } for (i = p;i <= r;i++) { A[i] = templist[i]; //
临时数组中的元素依次赋值到A中 } } template<typename T> void MergeSort(T* list, int p, int r)
// 合并排序函数模板实现 { if (p < r) { int mid = (p + r) / 2; // 中点q MergeSort(list, p,
mid);// 递归地归并排序左半部分 MergeSort(list, mid + 1, r); // 递归地归并排序右半部分 Merge(list, p,
mid, r);// 递归地左右两部分合并 } } template<typename T> void Array<T>::mergeSort() //
类合并函数的实现 { MergeSort(list, 0, size-1); // 调用MergeSort函数模板 } template<typename T>
void QuickSort(T* A, int start, int end) // 快速排序函数模板 { int i = start + 1, j =
end;// 以开头为"枢纽元" while (i < j) { while (A[j] > A[start]) // 从后往前，寻找一个比"枢纽元"小的数
j--;while (A[i] < A[start]) // 从前往后，寻找一个比"枢纽元"大的数 i++; if(i < j) mySwap(A[i],
A[j]);// 交换两个数的位置 } mySwap(A[start], A[j]); // 交换"枢纽元"与最后一个比它小的值的位置 if (--j >
start) QuickSort(A, start, j);// 递归地对前面都比"枢纽元"小的元素进行快速排序 if (i < end)
QuickSort(A, i, end);// 递归地对前面都比"枢纽元"大的元素进行快速排序 } template<typename T> void
Array<T>::quickSort()// 类成员快速排序函数实现 { QuickSort(list, 0, size - 1); // 调用快速排序模板
}template<typename T> void print(Array<T> a) { cout << "The array contents:" <<
endl;for (int i = 0;i < a.size;i++) { cout << a[i] << " "; } cout << endl; } int
main() {const int rawdata[] = { 19, 13, 9, 8, 23, 39, 4, 2, 75, 100, 43, 27};
Array<int> myArray(sizeof(rawdata)/sizeof(int)); for (int i = 0;i < sizeof
(rawdata) /sizeof(int);i++) { myArray[i] = rawdata[i]; //
将原始数据填充到Array类模板的对象myArray中 } print(myArray); // 打印原始数组 Array<int>
copyMyArray1(myArray);// 调用复制构造函数创建一个myArray副本1 cout << "After insert sort, ";
copyMyArray1.insertSort();// 使用插入排序对副本进行选择排序 print(copyMyArray1); Array<int>
copyMyArray2 = myArray;// 使用重载运算符"="创建myArray副本2 cout << "After bubble sort, ";
copyMyArray2.bubbleSort();// 使用冒泡排序对副本2进行排序 print(copyMyArray2); Array<int>
copyMyArray3 = myArray;// 创建副本 cout << "After selection sort, The array
contents: \n"; int* a = (int*)copyMyArray3; // 将副本转换为int类型的指针（数组首元素指针）
SelectSort(a, copyMyArray3.getSize());// 利用重载之后的选择排序函数进行排序 for (int i = 0;i <
copyMyArray3.getSize();i++) {cout << *(a+i) << " "; // 打印排序后数组 } cout << endl;
cout << "After selection sort, "; // 使用类的成员函数SelectSort对副本对象copyMyArray3进行选择排序
copyMyArray3.selectSort(); print(copyMyArray3); Array<int> copyMyArray4 =
myArray;cout << "After shell's sort, "; // 使用希尔排序对副本4进行排序
copyMyArray4.shellSort(); print(copyMyArray4); Array<int> copyMyArray5 =
myArray;cout << "After heap sort, "; // 使用堆排序对副本5进行排序 copyMyArray5.heapSort();
print(copyMyArray5); Array<int> copyMyArray6 = myArray; cout << "After merge
sort, "; // 使用堆排序对副本6进行排序 copyMyArray6.mergeSort(); print(copyMyArray6); Array<
int> copyMyArray7 = myArray; cout << "After quick sort, "; // 使用快速排序对副本7进行排序
copyMyArray7.quickSort(); print(copyMyArray7); system("pause"); return 0; }
* 操作运行结果 The array contents: 19 13 9 8 23 39 4 2 75 100 43 27 After insert
sort, Thearray contents: 2 4 8 9 13 19 23 27 39 43 75 100 After bubble sort, The
array contents: 2 4 8 9 13 19 23 27 39 43 75 100 After selection sort, The array
contents:2 4 8 9 13 19 23 27 39 43 75 100 After selection sort, The array
contents:2 4 8 9 13 19 23 27 39 43 75 100 After shell's sort, The array
contents:2 4 8 9 13 19 23 27 39 43 75 100 After heap sort, The array contents: 2
4 8 9 13 19 23 27 39 43 75 100 After merge sort, The array contents: 2 4 8 9 13
19 23 27 39 43 75 100 After quick sort, The array contents: 2 4 8 9 13 19 23 27
39 43 75 100 请按任意键继续. . .

热门工具换一换