資料結構 — 排序算法（基礎）

1、直接插入排序

/*插入排序*/
void insertion_sort (element arr[], int n) {
  int i,j;
  element next;
  for(i = 1; i<n; i++) {
    /*要插入的元素*/
    next = arr[i];
    /*找要插入元素next的 插入位置*/
    for(j = i-1; j>=0 && next<arr[j]; j--) {
      arr[j+1] = arr[j];
    }
    /*插入*/
    arr[j+1] = next;
  }
}      

2、希爾排序（插入）

<span style="font-size:14px;">void shell_sort(element arr[], int n) {
  int i, j;
  int dis = n/2;
  while(dis >= 1) {
    for(i = dis; i<n; i++) {
      element next = arr[i];
      //next如果小，就一直向右移動，否則将next指派給 該位置的後面一位
      for(j = i - dis; next<arr[j] && j>=0; j = j-dis) {
        arr[j+dis] = arr[j];
      }
      arr[j+dis] = next;
    }
    dis /= 2;
  }
}</span>      

3、冒泡排序（交換）

void bubble_sort(element arr[], int n) {
  int i, j;
  for(i = 0; i<n; i++) {
    for(j = 0; j<n-i-1; j++){
      if(arr[j]>arr[j+1]) {
        arr[j] = arr[j] + arr[j+1] - (arr[j+1] = arr[j]);
      }
    }
  }
}      

4、快速排序（交換）

/*快速排序（交換）*/
void quick_sork(element arr[] ,int left ,int right) {
  int i, j;
  element pivot, temp;
  
  if(left < right) {
     //i控制最左邊，j控制最右邊
    i = left;
    j = right;
    //最左邊的元素為參考點
    pivot = arr[left];
    /*
      1.從左邊找到第一個大于pivot的元素
      2.從右邊找到第一個小于pivot的元素
      3.如果i<j 交換兩個值
    */
    do {
      do
        i++;
      while(arr[i]<pivot);
      
      do 
        j--;
      while(arr[j]>pivot);
      
      if(i<j){
        arr[i] = arr[i] + arr[j] - (arr[j] = arr[i]);
      }
    }while(i < j);
    //将pivot放入位置j
    arr[left] = arr[left] + arr[j] - (arr[j] = arr[left]);
    /*
      現在是左邊的元素全部小于 pivot 右面的元素全部大于 pivot
      1.left,j-1
      2.j+1,right
    */
    quicksork(arr, left, j-1);
    quicksork(arr, j+1, right);
  }
}      

/*選擇排序*/
void select_sort(element arr[], int n) {
  int i, j;
  int min;
  for(i = 0; i<n; i++) {
    min = i;
    //找到最小值的下标
    for(j = i+1; j<n; j++) {
      if(arr[min]>arr[j]) {
        min = j;
      }
    }
    //從所有序列中先找到最小的，然後放到第一個位置
    arr[i] = arr[i] + arr[min] - (arr[min] = arr[i]);
  }
}