氣泡排序 (Bubble Sort)
i 和 i+1 比,比較大的往後。
經過一輪後,最大的會在最後面,下一論則不比較已經排好的。
//declare arr[size]
for(i=size-1; i>=1; i--) //當i=1時,j只做0和1。
for(j=0; j<i; j++)
if(arr[j] > arr[j+1])
//switch
效率:O(n²)
插入排序 (Insertion Sort)
第1個元素不用排,在已排序區,其他都在未排序區。
從第2個元素開始,插到已排序區。在已排序區中,從尾端往回比較大小排序。
for(i=1; i<size; i++){
insert = arr[i];
j=i-1; //往回比大小
while(j>=0 && arr[j]>insert){
arr[j+1] = arr[j]; //insert還獨立在外面
j--;
}
arr[j+1] = insert; //while()退出時會-1,所以要+1
}
效率:O(n²)
合併排序 (Merge Sort)
#include <bits/stdc++.h>
using namespace std;
#define size 6
void merge(int *arr, int L, int M, int R){
int left = L; //左半部執行到第幾個
int right = M+1;
int tmp[size], i=L; //i是陣列tmp的索引值
while((left<=M)&&(right<=R)){ //代表還有元素可以合併
if(arr[left]<arr[right])
tmp[i++]=arr[left++];
else tmp[i++]=arr[right++];
}
while(left<=M) //代表還有剩餘元素需要放入陣列tmp
tmp[i++]=arr[left++];
while(right<=R)
tmp[i++]=arr[right++];
for(i=L; i<=R; i++)
arr[i] = tmp[i];
}
void mergesort(int *arr, int L, int R){
int M;
if(L<R){
M = (L+R)/2;
mergesort(arr, L, M); //切割成左半部
mergesort(arr, M+1, R);
merge(arr, L, M, R);
}
}
int main(){
int arr[size] = {3,2,5,1,4,6};
mergesort(arr, 0, size-1);
for(int i=0; i<size; i++)
cout << arr[i] << " ";
}
效率:O(n log(n))
快速排序 (Quick Sort)
效率:O(n log(n))
選一個 pivot 為基準,找出 i 和 j。
i 為由前往後第一個 > pivot 的,j 為由後往前第一個 < pivot 的。
找到 i 和 j 後,如果 i ≤ j,i 與 j 互換。
如果 j 在 i 的左邊或 i 和 j 相同,pivot 與 j 互換,此時 pivot 已排序完畢。
以 pivot 的左半部與右半部分成兩部分,重複以上步驟。
//Quick Sort
#include <stdio.h>
#define size 10
void quicksort(int *arr, int l, int r){
int i=l, j=r+1, tmp;
if(l<r){
while(i<j){
while(arr[++i] < arr[l]);
while(arr[--j] > arr[l]);
if(i>=j) break;
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
tmp = arr[j];
arr[j] = arr[l];
arr[l] = tmp;
quicksort(arr, l, j-1);
quicksort(arr, j+1, r);
}
}
int main(){
int arr[size] = {7,1,8,3,5,2,9,6,0,4};
quicksort(arr, 0, size-1);
int i;
for(i=0; i<size; i++)
printf("%d ", arr[i]);
}