要排序的例子：
8 6 2 3 1 5 7 4
1.插入有break可以跳出循环，而选择排序只能无条件比完所有的，找出最大的或最小的。所以选择的时间复杂度是O（n^2），而插入有时候性能比O（nlogn）的算法更好。
- 选择排序
template<typename T>
void selectionSort(T arr[], int n)
{
for (int i = 0; i < n; i++)
{
//寻找[i,n)区间里的最小值
int minIndex = i;
for (int j = i + 1; j < n; j++)
{
if (arr[j] < arr[minIndex])
minIndex = j;
}
swap(arr[i], arr[minIndex]);
}
}
- 带break的插入排序
template<typename T>
void insertionSort(T arr[], int n){
for (int i = 1; i < n; i++){
//寻找元素arr[i]合适的插入位置
for(int j = i; j > 0; j--){
if (arr[j] < arr[j - 1])
swap(arr[j], arr[j - 1]);
else
break;
}
}
}
另一种更简洁的写法是：
template<typename T>
void insertionSort(T arr[], int n){
for (int i = 1; i < n; i++){
//寻找元素arr[i]合适的插入位置
for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--){
swap(arr[j], arr[j - 1]);
}
}
}
2.改进的思路：执行一次swap( )函数要进行三次赋值，如果不用它，让待排数找到正确的位置，直接一次赋值，性能应该会快一些。
！！！特别注意：判断条件要改成与e相比，arr[j-1]>arr[j] ---> arr[j-1]>e
- 改进后的插入排序：
template<typename T>
void insertionSort(T arr[], int n){
for (int i = 1; i < n; i++){
//寻找元素arr[i]合适的插入位置
T e = arr[i];
for (int j = i; j > 0 && arr[j - 1] > e; j--){
//显然arr[j-1]待在了偏前的位置，把它的值复制到后面去
arr[j] = arr[j - 1];
}
//不进入循环说明arr[i]找到了它的位置，即现在的j
arr[j] = e;
}
}
3.特别地，对于原先近乎有序的数组，插入排序表现十分强悍。当完全有序时，时间复杂度是O（n），内循环根本没进去。
- 冒泡排序和改进：
image
template<typename T>
void bubbleSort(T arr[], int n){
bool swapped;
do{
swapped = false;
for (int i = 1; i < n; i++)
if (arr[i - 1] > arr[i]){
swap(arr[i - 1], arr[i]);
swapped = true;
}
//优化，每一趟Bubble Sort都将最大的元素放在了最后的位置
//所以下一次排序，最后的元素可以不再考虑
n--;
} while (swapped);
}
image
优化：记录最后一次交换的位置，之后的元素不再考虑
//优化的冒泡排序
template<typename T>
void bubbleSort2(T arr[], int n){
int newn; //使用newn进行优化
do{
newn = 0;
for (int i = 1; i < n; i++)
if (arr[i - 1] > arr[i]){
swap(arr[i - 1], arr[i]);
//记录最后一次的交换位置
//在此之后的元素不再考虑
newn = i;
}
n = newn;
} while (newn > 0);
}
网友评论