排序算法

Posted on   |   In   |  

c语言中快排的实现

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <iostream>

using namespace std;

void myqsort(int *a, int left, int right)
{
    if (left >= right) return;

    int last = left;
    int mid = left + (right- left)/2;
    swap(a[mid], a[left]);
    for(int i = left +1; i<= right; i++){
        if (a[i] < a[left])
            swap(a[i],a[++last]);        //此处始终保证了last所指向的元素的后一个元素大于等于划分点，并且(left +1, last)的所有元素小于划分点
    }
    swap(a[left], a[last]);

    myqsort(a, left, last -1);
    myqsort(a, last + 1, right);
}

int main()
{
    int arr[] ={9,4,1,2,3,81,1,2,3,91,99,8,7,8,5};
    int length = sizeof(arr)/sizeof(int);

    for(int i= 0 ; i < length; ++i){
        printf("%d ", arr[i]);
    }
    myqsort(arr, 0, length -1);
    printf("\n after sort:\n");
    for(int i= 0 ; i< length; ++i){
        printf("%d ", arr[i]);
    }
}