1. 冒泡排序
冒泡排序，依序比较相邻的两个，顺序不对则交换
时间复杂度 O(n^2)
void bsort(int a[], n){
for(int i=0; i<n; i++){
for(int j=0; j<n-i-1; j++){
if(a[j]>a[j+1]){
temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
}
}
}
}
2. 选择排序，selection sort
选择排序，从第一个元素开始往后遍历，每轮从后面选择最小的元素排到最前面。
时间复杂度 O(n^2),排序速度先慢后快，因为要查找的元素的元素逐个减少。大量查找，少量移动。
void selectsort(int a[], n ){
for(int i=0; i<n; i++){
min = a[i];
for(int j = i+1; j<n; j++){
if(a[j]<min){
int temp;
temp = min;
min = a[j];
a[j] = temp;
}
}
a[i] = min;
}
}
3. 插入排序 insertion sort
将序列分为已排序和未排序两个部分，对未排序部分依序遍历插入前面已排序部分。
先快后慢。后几轮插入时要比较的更多。
- 可以假设认为第一个元素是已排序的
-
依序对后面的n-1个元素遍历，
for i in 1 - n:
将第i个元素插入前面i-1个已排序元素中void insertionsort(int a[], int n ){ for(int i=1; i<n; i++){ int temp = a[i]; for(int j=i-1;j>=0;j--){ if(a[j]>temp) a[j+1] = a[j]; else{ a[j+1] = temp; break; } } } }
4. 归并排序
归并排序要调用递归的方法,步骤：
- 排序好左边，MergeSort(left),对左边序列递归调用这三个步骤
- 排序好右边，Mergesort(right)，对右边序列递归调用这三个步骤
- 合并两个有序序列， Merge(v, left, right)
时间复杂度 O(nlogn)，空间上需要额外的 n 个空间，不利于基本有序的序列。
void merge(int a[], int low, int mid, int high, int temp[]){
int i =low;
int j = mid+1;
int k =0;
while(i <=mid && j<=high){
if(a[i]<a[j]){
temp[k++]=a[i];
i++;
}
else{
temp[k++]=a[j];
j++;
}
}
while(i<=mid){
temp[k++] = a[i];
i++;
}
while(j<=high) {
temp[k++] = a[j];
j++;
}
for(int i=0; i<k; i++){
a[i+low] = temp[i];
}
}
void mergesort(int a[], int low, int high, int temp[] ){
if(low<high){
int mid = (high+low)/2;
mergesort(a, low, mid,temp);
mergesort(a, mid+1, high,temp);
merge(a, low, mid, high,temp);
}
}
5. 快速排序
也是要用到递归
- 选择某个位置的元素 p
- 将大于该元素的放到 p 的右边， 小于 p 的放到左边。
- 递归调用这三步分别对p左边和p右边的元素进行排序
时间复杂度 O(nlogn)，相对归并排序不需要额外的空间，p 的选择对排序影响比较大，序列基本有序时会相对快。
int partition(int a[], int low, int high){
int midvalue = a[low];
int i = low;
int j = high;
while(i<j){
while(a[j]>midvalue && i<j)
j--;
if(i<j)
a[i++] = a[j];
while(a[i]<midvalue && i<j)
i++;
if(i<j)
a[j--] = a[i];
}
a[i]=midvalue;
return i;
}
void quicksort(int a[], int low, int high){
if(low<high){
int pivot = partition(a, low, high);
quicksort(a, low, pivot-1);
quicksort(a, pivot+1, high);
}
}
5. 堆排序
大根堆： 父节点比两个子节点都大，小根堆反之。
//调整以第i个节点为父节点的树，使之成为大根堆
int adjust_heap(vector<int> &v, int length, int i){
int left = 2 * i;
int right = 2 * i + 1;
int largest = i;
int temp;
while(left < length || right < length){
if (left < length && v[largest] < v[left]){
largest = left;
}
if (right < length && v[largest] < v[right]){
largest = right;
}
if (i != largest){
temp = v[largest];
v[largest] = v[i];
v[i] = temp;
i = largest;
left = 2 * i;
right = 2 * i + 1;
}
else{
break;
}
}
}
//建立堆，使首节点最大。从最后一个非叶子节点开始，逐个向前，调整为大根堆
int build_heap(vector<int> &v, int length){
int i;
int begin = length/2 - 1; //get the last parent node
for (i = begin; i>=0; i--){
adjust_heap(v,length,i);
}
}
int heap_sort(vector<int> &v){
int length = v.size();
int temp;
build_heap(v,length);
for(int i=n-1;i>=0;i--)
//交换v[0]和v[i]
temp = v[i];
v[i] = v[0];
v[0] = temp;
i--;
//调正前 i-1 个元素是大根堆来获取前i-1的最大值
adjust_heap(v,i,0);
}
}
6. 希尔排序
其实就是分段的插入排序