快速排序

#include <stdlib.h>
#include <stdio.h>

int len = 8;

void quick_sort_iter(int*, int, int);

void printArray(int array[], int len) {
    for(int i = 0; i < len; i++) {
        printf("%d ", array[i]);
    } 
    printf("\n");
}

void swap(int arr[], int i, int j) {
  printf("swap %d, %d\n", i, j);
  int tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
}

int main() {
  int toTest[] = {3, 1, 4, 5, 10, 6, 5, 100};
  quick_sort_iter(toTest, 0, len - 1);

  /* swap(toTest, 0, 1); */
  printArray(toTest, len);
  exit(0);
}


void quick_sort_iter(int arr[], int start, int end) {
  printArray(arr, len);
  if (start >= end) return;

  int left = start;
  int right = end - 1;
  int middle = arr[end];

  // 经过步骤之后left之前的都是小于middle。右边都是大于middle
  while (left < right) {
    while (arr[left] < middle && arr[left] <= arr[right]) {
      left++;
    }
    while (arr[right] >= middle && arr[left] < arr[right]) {
      right--;
    }
    swap(arr, left, right);
  }

  if (arr[left] >= middle) {
    swap(arr, left, end);
  } else {
    ///这种情况是middle是最大的元素，到了这里left = end - 1了。
    // 因为这里arr[left] < middle。如果left不为end-1的话，left会继续往右走。因为left先走，所以不存在right往右走了多于一格的情况
    // 因为如果right往右走了一个，arr[left]会大于或等于middle。或是上面那种情况
    left++;
  }

  if (left > 0) {
    quick_sort_iter(arr, start, left - 1);
  }
  quick_sort_iter(arr, left + 1, end);
}