数据结构与算法

常见算法

Bubble Sort (冒泡法) (i, j, j < len - 1 - i)

int arr[5] = {3, 1, 4, 5, 2};
bubbleSort(arr, 5);
void bubbleSort(int arr[], int len)
{
   int i, j, temp;
   for (i = 0; i < len; i++) {
     for (j = 0; j < len - 1 - i; j++) {
        if(arr[j] > arr[j + 1]) { // > 升序， < 降序
          temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j+1] = temp;
        }
     }
   }
}

Insertion Sort (插入排序） (j , p, j > 0 && arr[j - 1] > tmp)

int arr[5] = {3, 1, 4, 5, 2};
InsertionSort(arr, 5);
void InsertionSort(int arr[], int len)
{
    int j, p;
    for (p = 1; p < len; p++) {
        int tmp = arr[p];
        for (j = p; j > 0 && arr[j - 1] > tmp; j--) { 
            arr[j] = arr[j - 1];
        }
        arr[j] = tmp;
    }
}

Shell Sort(希尔排序） (increment, j >= increment; arr[j - increment], break)

int arr[5] = {3, 1, 4, 5, 2};
ShellSort(arr, 5);
void ShellSort(int arr[], int len)
{
    int i, j, increment;
    for (increment = len / 2; increment > 0; increment /=  2) { // loop increment
        for ( i = increment; i < len; i ++) {                   // loop i
            int tmp = arr[i];                                   // TMP
            for (j = i; j >= increment; j -= increment) {       // loop j (>=)
                if (arr[j] < arr[j - increment]) {              // Judge (j - increment)
                    arr[j] = arr[j - increment];                // Exchange
                } else {
                    break;                                      // Break **
                }
            }
            arr[j] = tmp;                                       // TMP exchange
        }
    }
}

Dutch National Flag Problem （荷兰旗子问题） (begin, current, end)

char bails[9] = {'r', 'b', 'r', 'w', 'w', 'r', 'b', 'w', 'b'};
sort(bails, 9)
void sort(char Arr[], int N)
{
  int begin, current, end;
  begin = current = 0;
  end = N - 1;
  while (current <= end) {
    if (Arr[current] == 'r') {
      swap(&Arr[current], &Arr[begin]);
      current++;
      begin++;
    } else if (Arr[current] == 'w') {
      current++;
    } else {
        swap(&Arr[current], &Arr[end]);
      end--;
    } 
  } 
}
void swap(char *A, char *B)
{
    char tmp = *A;
    *A = *B;
    *B = tmp;
}

Quickly Sort (快速排序）

int arr[5] = {3, 1, 4, 5, 2};
quicklySort(arr, 0, 4);  // [left , right] 区间内排序
void quicklySort(int arr[], int left, int right)
{
    if (left > right) {
        return;
    }
    
    int i = left;
    int j = right;
    int key = arr[left];
    
    while (i < j) {
        
        while (i < j && key <= arr[j]) {       // 如果降序 改为 >=
            j--;
        }
        
        arr[i] = arr[j];
        
        while (i < j && key >= arr[i]) {    // 如果降序 改为 <=
            i++;
        }
        arr[j] = arr[i];
    }
    arr[i] = key;
    quicklySort(arr, left, i - 1);
    quicklySort(arr, i + 1, right);
}