冒泡排序
=================================================
每次遍历把unsorted里最大的那个堆到最右。
最基本的一种排序，可以看出真的是挺慢的。
伪代码如下：
do
swapped = false //无序数列
for i = 1 to indexOfLastUnsortedElement-1//遍历无序数列
if leftElement > rightElement //比较相邻两个元素
swap(leftElement, rightElement)
swapped = true
while swappedC++代码：
#include <bits/stdc++.h>
using namespace std;
void Swap(int A[], int i, int j){
A[i] = A[i] + A[j];
A[j] = A[i] - A[j];
A[i] = A[i] - A[j];
}
void BubbleSort(int A[],int n){
for(int i = 0; i < n; i++){
for(int j = 0; j < n - i -1; j++){
if(A[j] > A[j+1]){
Swap(A, j, j+1);
}
}
}
}
int main() {
int n;
int s[105];
cin >> n;
for(int i = 0; i < n; i++){
cin >> s[i];
}
BubbleSort(s, n);
for(int i = 0; i < n; i++){
cout << s[i] << " ";
}
return 0;
}很容易看出复杂度是O(n2)。
写得比较麻烦，主要是为了引出下面这个问题=。=
当我下面这样写，很简洁，但是会出错。有谁能告诉我为什么？(手动滑稽)
void Swap(int a, int b){
a = a + b;
b = a - b;
a = a - b;
}
void BubbleSort(int A[],int n){
for(int i = 0; i < n; i++){
for(int j = 0; j < n - i -1; j++){
if(A[j] > A[j+1]){
Swap(A[j], A[j+1]);
}
}
}
}选择排序
=================================================
每次遍历unsorted，选出最小的那个标记，分别与未遍历完的比较，遍历完一次，堆到sorted最右。
伪代码如下：
repeat (numOfElements - 1) times
set the first unsorted element as the minimum//选定unsorted的第一个元素
for each of the unsorted elements//遍历unsorted
if element < currentMinimum//分别比较
set element as new minimum
swap minimum with first unsorted position错误的C++代码：
#include <bits/stdc++.h>
using namespace std;
void Swap(int A[], int i, int j){
A[i] = A[i] + A[j];
A[j] = A[i] - A[j];
A[i] = A[i] - A[j];
}
void SelectionSort(int A[], int n){
int pos;
for(int i = 0; i < n; i++){//1 2 3 5
pos = i;
for(int j = i+1; j < n; j++){
if(A[j] < A[pos]){
pos = j;
}
}
Swap(A, i, pos);
}
}
int main() {
int n;
int s[105];
cin >> n;
for(int i = 0; i < n; i++){
cin >> s[i];
}
SelectionSort(s, n);
for(int i = 0; i < n; i++){
cout << s[i] << " ";
}
return 0;
}时间复杂度也是O(n2)。
里面有一句非常隐蔽的bug，瞅了我一个小时
乱骚的代价-_-||
插入排序
=================================================
选定unsorted的第一个元素，遍历sorted的每个元素比较，直到找到合适的位置，插入。
伪代码如下：
mark first element as sorted
for each unsorted element X
'extract' the element X//选定X
for j = lastSortedIndex down to 0//遍历sorted
if current element j > X//对每一个unsorted都与X比较
move sorted element to the right by 1
break loop and insert X hereC++代码：
#include <bits/stdc++.h>
using namespace std;
void InsertionSort(int A[], int n){
int temp;
for(int i = 1; i < n; i++){
temp = A[i];
for(int j = i; j > 0; j--){
if(temp < A[j-1]){
A[j] = A[j-1];
if(i = 1){//此处如果不把第一个元素特殊处理
A[j-1] = temp;//则在第一个元素比第二个元素大的情况下
}//把A[0]赋值给每个元素
}else{
A[j] = temp;
break;
}
}
}
}
int main(){
int n;
int s[105];
cin >> n;
for(int i = 0; i < n; i++){
cin >> s[i];
}
InsertionSort(s, n);
for(int i = 0; i < n; i++){
cout << s[i] << " ";
}
return 0;
}看出时间复杂度是O(n2)。