1. 交换排序
根据数组中两个元素值的大小来交换两个元素在数组中的位置。
1.1 冒泡排序
1.1.1 基本思想： 假设待排序的长度是n，从后往前（或者是从前往后）依次比较相邻的两个元素的大小，
如果是逆序，则交换，直到比较完成。下面是从小到大的排序过程：
(1) 取未排序序列的最后一个元素（待排序的元素）；
(2) 在未排序的元素序列中从后向前扫描，如果待排序的元素比新元素小，就交换它们两个；
(3) 重复步骤(2)，直到待排序的元素插入与排序的位置；
(4) 重复步骤(1)~(3)，知道排序完成。
1.1.2 代码实现：
void bubbleSort(vector<int> &arr, int len){
for(int i=0; i < len-1; i++){ // n-1趟排序
int flag = 0; // 交换的标记
for(int j=len-1; j>i; j--){
if(arr[j] < arr[j-1]){
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
flag = 1;
}
}
if(flag == 0) //第一次排序为发生交换，则原序列有序
return;
}
}
1.2.3 性能分析：
(1) 空间复杂度：。
(2) 时间复杂度：最好情况下（待排序的序列为有序序列，比较次，交换
次），为
。最坏情况下（待排序序列为逆序序列，比较
次，交换
次）：
。
(3) 稳定性：当相等的两个元素进行比较时，不会发生交换，两个元素在排序前和排序后的相对位置不会发生交换。因此，针对以上所写冒泡排序算法，是稳定的。
1.2 快速排序
1.2.1 基本思想： 基于分治法。在待排序表L[1,...,n]中任取一个元素pivot为基准，通过一趟排序将序列划分为两部分：L[1,...,k-1]和L[k+1,...,n]，使得L[1,...,k-1]的所有元素值都小于pivot，L[k+1,...,n]的所有元素值都大于pivot，而pivot在序列最终的L[k]位置上。随后，分别递归的对两个子序列重复以上过程，直到序列内只有一个元素或者为空。由此可知，每一趟的快速排序都有一个元素在序列的最终位置上。
1.2.2 代码实现：
int partition(vector<int> &arr, int low, int high){
int pivot = arr[low];
while(low < high){
while(low<high && arr[high] >= pivot)
--high;
if(low<high)
arr[low++] = arr[high];
while(low<high && arr[low]<=pivot)
++low;
if(low < high)
arr[high--] = arr[low];
}
arr[low] = pivot;
return low;
}
void quickSort(vector<int> &arr, int low, int high){
if(low < high){
int pivotPos = partition(arr, low, high);
quickSort(arr, low, pivotPos - 1);
quickSort(arr, pivotPos + 1, high);
}
}
1.2.3 性能分析：
(1) 空间复杂度：快速排序需要递归栈保存每次递归调用时所需要的信息，为。（可借助二叉树的思想）
(2) 时间复杂度：快速排序的时间复杂度与划分是否对称有关。最好的情况下，每次划分后的序列是对称的，时间复杂度为；最坏的情况下，初始序列是有序或是逆序，时间复杂度为
。
(3) 稳定性：举例，初始序列为{2，2，3}，快速排序后为{2，2，3}。值相同的两个元素在序列中的相对位置发生了变化。
2. 插入排序
插入排序：每次将一个待插入的元素插入到已经排序好的子序列中，直到全部的序列插入完成。
2.1 直接插入排序
2.1.1 基本思想：
假设L是一个由n个元素的待排序序列，现将L(i)插入到有序列L[1,2,...,i-1]中，则排序过程如下：
(1) 查找L(i)在L[1,2,...,i-1]中待插入的位置k；
(2) 将L[k,...,i-1]中的所有元素往后移动一个位置；
(3) 将L(i)复制到L(k)中；
(4) 重复步骤(1)-(3)，直到所有的元素排序完成。
2.1.2 代码实现：
void insertSort(vector<int> &arr, int len){
for(int i = 1; i < len; i++){
int current = arr[i];
int j = i - 1;
while(j >= 0 && current < arr[j]){
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = current;
}
}
2.1.3 性能分析：
(1) 空间复杂度： 借助了常数个存储单元，空间复杂度为；
(2) 时间复杂度： 直接插入排序的时间复杂度与待排序序列的初始状态有关。最好情况下，待排序序列有序，每个元素需要比较1次，时间复杂度为；最坏的情况下，待排序序列逆序，总的比较次数为
，总的移动次数为
.因此，时间复杂度为
。
(3) 稳定性：待插入的元素再有序序列中查找待插入的位置时，遇到相同元素即停止，不会发生交换。因此，直接插入排序是稳定的。
2.2 折半插入排序
2.2.1 基本思想：
假设L是一个由n个元素的待排序序列，现将L(i)插入到有序列L[1,2,...,i-1]中，则排序过程如下：
(1) 折半查找L(i)在L[1,2,...,i-1]中待插入的位置k；
(2) 将L[k,...,i-1]中的所有元素往后移动一个位置；
(3) 将L(i)复制到L(k)中；
(4) 重复步骤(1)-(3)，直到所有的元素排序完成。
2.2.2 代码实现：
void binaryInsertSort(vector<int> &arr, int len){
int left, right, mid, temp;
for(int i = 1; i < len; i++){
temp = arr[i]; //待插入元素
left = 0;
right = i - 1;
while(left <= right){
mid = (left + right) / 2;
if(temp < arr[mid])
right = mid - 1;
else
left = mid + 1;
}
for(int j = i - 1; j > right; j--)
arr[j + 1] = arr[j];
arr[right + 1] = temp;
}
}
2.2.3 性能分析：
(1) 空间复杂度：。
(2) 时间复杂度：。第
趟折半查找待插入元素的在已排序序列中位置的时间复杂度为
，则总的比较次数为
；总的移动次数为
。所以折半插入排序的时间复杂度为
。
(3) 稳定性：折半插入排序是稳定的。
主函数代码：
#include <iostream>
#include <vector>
using namespace std;
int main(){
int len;
cin >> len;
vector<int> arr(len);
cout << "待排序序列为：";
for(int i = 0; i < len; i ++){
cin >> arr[i];
}
// bubbleSort(arr, len);
// quickSort(arr, 0, len - 1);
// insertSort(arr, len);
// binaryInsertSort(arr, len);
cout << "排序结果为：";
for(int i = 0; i < len; i ++){
cout << arr[i] << ' ';
}
cout << endl;
return 0;
}
网友评论