快速排序

步骤

1 确定分界点

• 开始 | 中间值 | 随机值
  2 调整区间
• 第一区间小于（X）
• 第二区间大于等于（X）
  3 递归处理左右两边

快速排序思路

代码模板

void quick_sort(int q[], int l, int r) {  
    if (l >= r) return;  
    int x = q[(i+j+1)/2], i = l - 1, j = r + 1;  
    while (i < j) {  
        do i++; while (q[i] < x);  
        do j--; while (q[j] > x);  
        if (i < j) swap(q[i], q[j]);  
    }  
    quick_sort(q, l, i-1);  
    quick_sort(q, j + 1, r);  
}

if (l >= r) return;  

首先进行边界判断，如果指针不同则直接退出

while (i < j) {  
        do i++; while (q[i] < x);  
        do j--; while (q[j] > x);  
        if (i < j) swap(q[i], q[j]);  
    }  

循环判断左右两边如果数值大于设置的中间值，则进行左右两边的数据交换

quick_sort(q, l, i-1);  
   quick_sort(q, j + 1, r);  

不断进行递归来不断地分区的将左右两边的数据进行换算，不断重复

代码模板

void quick_sort(int q[], int l, int r) {  
    if (l >= r) return;  
    int x = q[(i+j+1)/2], i = l - 1, j = r + 1;  
    while (i < j) {  
        do i++; while (q[i] < x);  
        do j--; while (q[j] > x);  
        if (i < j) swap(q[i], q[j]);  
    }  
    quick_sort(q, l, i-1);  
    quick_sort(q, j + 1, r);  
}

if (l >= r) return;  

首先进行边界判断，如果指针不同则直接退出

while (i < j) {  
        do i++; while (q[i] < x);  
        do j--; while (q[j] > x);  
        if (i < j) swap(q[i], q[j]);  
    }  

循环判断左右两边如果数值大于设置的中间值，则进行左右两边的数据交换

quick_sort(q, l, i-1);  
   quick_sort(q, j + 1, r);  

不断进行递归来不断地分区的将左右两边的数据进行换算，不断重复