Ｏ（n^2）
选择排序
#include <iostream>using namespace std;template <typename T>void selectionSort(T arr[], int n){for(int i = 0; i < n; i++){int minIndex = i;for(int j = i + 1; j < n; j++){if( arr[j] < arr[minIndex] )minIndex = j;}swap(arr[minIndex], arr[i]);}}
插入排序
#include <iostream>using namespace std;template <typename T>void insertionSort(T arr[], int n){// for(int i = 1; i < n; i++){//// for(int j = i; j > 0 && arr[j] < arr[j-1]; j--){// swap( arr[j], arr[j-1] );// }// }//插入排序优化------将交换改为赋值for(int i = 1; i < n; i++){T e = arr[i];int j; //ｊ存放元素e应该插入的位置for(j = i; j > 0 && arr[j-1] > e; j--){arr[j] = arr[j-1];}arr[j] = e;}}
冒泡排序
#include <iostream>using namespace std;template<typename T>void old_bubbleSort(T arr[], int n){for(int i = 0; i < n; i++){for(int j = n - 1; j > 0; j--){if( arr[j] < arr[j-1] )swap(arr[j], arr[j-1]);}}return;}template<typename T>void bubbleSort( T arr[], int n){// 基础冒泡排序// 比较相邻的元素。如果第一个比第二个大，就交换他们两个。// 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。// 针对所有的元素重复以上的步骤，除了最后一个。// 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。// for(int i = 0; i < n; i++){// for(int j = n - 1; j > 0; j--){// if( arr[j] < arr[j-1] )// swap(arr[j], arr[j-1]);// }// }//冒泡排序优化(借鉴插入排序－－可以提前结束)bool flag = true;for(int i = 0; i < n && flag; i++){flag = false;for(int j = n-1; j > 0; j--){if(arr[j] < arr[j-1]){swap(arr[j], arr[j-1]);flag = true;}}}return;}
希尔排序－－－－－插入排序的衍生（最优到Ｏ（ｎ^(3/2)））
#include <iostream>using namespace std;template<typename T>void shellSort( T arr[], int n ){int h = 1;while( h < n/3 )h = 3 * h + 1;// 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...while( h >= 1 ){// h-sort the arrayfor( int i = h ; i < n ; i ++ ){// 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序T e = arr[i];int j;for( j = i ; j >= h && e < arr[j-h] ; j -= h )arr[j] = arr[j-h];arr[j] = e;}h /= 3;}return;}