冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void swap(int &a,int &b){
    int temp=a;
    a=b;
    b=temp;
}

void BubbleSort(int A[];int n){
    for(int i=0;i<n-1;i++)
        bool flag=false;
        for(int j=n-1;j>i;j--)
            if(A[j-1]>A[j]){
                swap(A[j-1],A[j]);
                flag=true;
            }
         if(flag==false)
            return;       //本趟遍历后没有发生交换，说明表已经有序，可以结束算法
}

  • 稳定

  • 可用于链表、顺序表

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int Partition(int A[];int low;int high){
    int pivot=A[low]
    while(low<high){
        while(low<high&&A[high]>=pivot) --high;
        A[low]=A[high]
    
    while(low<high && A[low]<=pivot)  ++low; 
        A[high] = A[low];
    }
    A[low]=pivot;
    return low;
}

void QuickSort(int A[];int low;int high){
    if(low<high){
        int pivotpos = Partition(A,low,high);
        QuickSort(A,low,pivotpos-1);
        QuickSort(A,pivotpos+1,high);
    }

}