C/C++選擇排序(Selection sort)

選擇排序：找到最小數值排到新的序列裡頭


輸入：未排序數序列
輸出：排序過後序列

最差時間複雜度 О(n²)
最優時間複雜度 О(n²)
平均時間複雜度 О(n²)

#include <stdio.h>


void soft(int a[], int length){
 for(int i = 0; i < length-2; i++){
  
  int min = i;

  for(int j = i + 1; j < length; j++){
   if(a[j]< a[min])
   {
    int temp = a[j];
    a[j] = a[min];
    a[min] = temp;
   }
  }
 }

 for(int i=0; i<length;i++){
  printf("%d\n", a[i]);
 }
}



int main(){
 int A[] = {98, 45, 68, 90, 29, 43, 17};
 int length = sizeof(A)/sizeof(int);
 soft(A,length);

 return 1;
}

C/C++ 插入排序(Insertion Sort)

插入排序：將已知序列分別依照數值大小去排序
例子：玩撲克牌會將手上排依照號碼大小分別插入相對的位址


輸入：n個數字的序列
輸出：排列好得序列

最差時間複雜度 O(n^2)
最優時間複雜度 O(n)
平均時間複雜度 O(n^2)
最差空間複雜度  O(n) ，需要輔助空間O(1)



虛擬碼：

INSERTION-SOFT(A)

for i ← 2 to length[A]
 do key ← A[i]

 j = i -1

 while j >0 and A[j] > key
  do A[j+1] ← A[j]
  j ← j-1

 A[j+1] ← key