1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <iostream>
#include <ctime>

using namespace std;

void swap(int &a,int &b){
    int tmp = a;
    a = b;
    b = tmp;
}

void printarr(int *a,int n){
    for(size_t i = 0; i < n; i++)
    {
        cout << a[i] << " ";
    }
    cout << endl;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void bubble_sort(int *a, int n){
    for(size_t i = n-1; i > 0;--i){
        for(size_t j = i; j > 0;--j)
        {
            if(a[j] < a[j-1])
                swap(a[j],a[j-1]);
        }
    }
}

void bubble_sort_speedup(int *a, int n){
    for(size_t i = 0; i < n-1; i++){
        int flag = 0;
        for(size_t j = 0; j < n-1-i; ++j){
            if(a[j] > a[j+1]){
                swap(a[j],a[j+1]);
                flag = 1;
            }
        }
        if(!flag)
            break;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

void cocktail_sort(int *a,int n){
    int left = 0;
    int right = n-1;
    while(left < right){
        for(size_t i = left; i<right;++i){
            if(a[i] > a[i+1])
                swap(a[i],a[i+1]);
        }
        right--;
        for(size_t j = right;j>left;--j){
            if(a[j-1] > a[j]){
                swap(a[j-1],a[j]);
            }
        }
        left++;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

void cocktail_sort_speedup(int *a,int n){
    bool sorted = false;
    while(!sorted){
        sorted = true;
        for( int i = 0; i < n - 1; i++ ){
            if( a[i] > a[i + 1] ){
                swap( a[i], a[i + 1] );
                sorted = false;
            }
        }
        if(sorted)
            break;
        sorted = true;
        for( int j = n - 1; j > 0; j-- ){
            if( a[j - 1] > a[j] ){
                swap( a[j], a[j - 1] );
                sorted = false;
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

void selection_sort(int *a, int n){
    for(size_t i = 0;i < n-1;i++){
        int index = i;
        for(size_t j = i+1;j < n;j++){
            if(a[j] < a[index])
                index = j;
        }
        if(i!=index)
            swap(a[i],a[index]);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

void insertion_sort(int *a, int n){
    for(size_t i = 1;i < n;i++){
        int tmp = a[i];
        size_t j = i;
        while(j > 0 && tmp < a[j-1]){
            a[j] = a[j-1];
            --j;
        }
        a[j] = tmp;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void shell_sort(int *a,int n){
    int h,i,j,t;
    for(h = n;h/=2;){
        // iterator
        for(i=h;i<n;i++){
            t=a[i];
            for(j=i;j>=h && t<a[j-h];j-=h){
                a[j] = a[j-h];
            }
            a[j] = t;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

void shell_sort_speedup(int *a,int n){
    int i,j,tmp,step;
    step = n;
    while(step>1){
        step = step/3+1;
        // insert sort
        for(i=step;i<n;i++){
            tmp = a[i];
            for(j=i;j>0 && a[j] < a[j-step];j-=step){
                a[j] = a[j-step];
            }
            a[j] = tmp;
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void merge_arr(int *a,int m,int n){
    int i,j,k;
    int *temp = new int[n];
    // 0 ---> n
    for(i=0,j=m,k=0;k<n;k++){
        temp[k] = j == n ?
            a[i++]:i == m ?
            a[j++]:a[j] < a[i]?
            a[j++]:a[i++];
    }
    for(k=0;k<n;k++){
        a[k] = temp[k];
    }
    delete [] temp;
}
void merge_sort(int *a,int n){
    if(n < 2)
        return;
    int m = n/2;
    merge_sort(a,m);
    merge_sort(a+m,n-m);
    merge_arr(a,m,n);
}

 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
37
38
39
40
41
42
43
44
45
46

void merge_arr2(int *a,int left,int mid,int right){
    int i = left;
    int j = mid + 1;
    int k = 0;
    int len = right-left+1;
    int *temp = new int[len];
    // while(i <= mid && j <= right){
    //     temp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
    // }
    // while(i <= mid){
    //     temp[k++] = a[i++];
    // }
    // while(j <= right){
    //     temp[k++] = a[j++];
    // }
    for(;k<len;k++){
        temp[k] = j > right?
                a[i++]:i > mid?
                a[j++]:a[i] < a[j]?
                a[i++]:a[j++];
    }
    for(k = 0; k< len;){
        a[left++] = temp[k++];
    }

    delete [] temp;
}
void merge_sort(int *a,int len){
    // int left,mid,right,n;
    int left,n;
    for(int i = 2;i/2 < len;i*=2){
        // left = 0;
        // for(left=0;left+i<len;){
        //     mid = left + i - 1;
        //     right = mid + i < len ? mid + i : len - 1;
        //     n = mid + i < len ? 2*i : len - left+1;
        //     merge_arr(a+left,mid,n);
        //     left = right + 1 ;
        // }
        for(left = 0;left < len;left+=i){
            // mid = left + i/2;
            n = left + i < len?i:len-left;
            merge_arr(a+left,i/2,n);
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

void quick_sort(int *a,int len){
    if(len<2)
        return;
    int i,j;
    int pivot = a[len/2];
    for(i=0,j=len-1;;i++,j--){
        while(a[i] < pivot) i++;
        while(a[j] > pivot) j--;
        if(i >= j) break;
        // swap value
        swap(a[i],a[j]);
    }
    quick_sort(a,i);
    quick_sort(a+i,len-i);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

void quick_sort2(int *a,int n){
    if(n<2) return;
    int mid=a[0]; // pivot
    int i=0,j=n-1;
    while(i<j){
        while(j>i && a[j]>=mid) j--;
        if(j>i){
            a[i]=a[j];
            i++;
        }
        while(i<j && a[i]<mid) i++;
        if(i<j){
            a[j]=a[i];
            j--;
        }
    }
    a[i]=mid;
    quick_sort2(a,i);
    quick_sort2(a+i+1,n-i-1);
}

 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

// i is index of array,the left child index is 2*i+1,the right one is 2*i+2,the father index is floor((i-1)/2)
void siftDown(int *a, int i, int n)
{
    int lhs=2*i+1;
    int rhs=2*i+2;
    int maxid=i;
    if(lhs<n && a[maxid]<a[lhs]) maxid=lhs;
    if(rhs<n && a[maxid]<a[rhs]) maxid=rhs;
    if(maxid!=i)
    {
        swap(a[i],a[maxid]);
        siftDown(a,maxid,n);
    }
}

// void makeHeap(int *a, int n){
//     for(int i=n/2-1; i>=0; i--)
//     {
//         siftDown(a,i,n);
//     }
// }

void heap_sort(int *a,int n){
    // makeHeap(a,n);
    for(int i=n/2-1; i>=0; i--){
        siftDown(a,i,n);
    }
    for(int i=n-1; i>0; i--){
        swap(a[0],a[i]);
        siftDown(a,0,i);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void heap_down(int *a,int i,int n){
    int lc = 2*i+1;
    for(;lc<n;i=lc,lc=2*i+1){
        // lc + 1 < n right chid index can't greater than the array length
        if(lc+1 < n && a[lc]<a[lc+1])
            lc++;
        if(a[i] >= a[lc])
            break;
        else
            swap(a[i],a[lc]);
    }
}

void heap_sort2(int *a,int n){
    // makeHeap(a,n);
    for(int i=n/2-1; i>=0; i--){
        heap_down(a,i,n);
    }
    for(int i=n-1; i>0; i--){
        swap(a[0],a[i]);
        heap_down(a,0,i);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void couting_sort(int *a,int n){
    int range = 20;
    int *C = new int[range];
    int *temp = new int[n];
    for(int i = 0;i < range;i++){
        C[i] = 0;
        if(i<n)
            temp[i]=0;
    }
    for(int j = 0;j < n;j++){
        C[a[j]]++;
    }
    for(int i = 1;i < range;i++){
        C[i]+=C[i-1];
    }
    for(int j = n-1;j >= 0;j--){
        temp[--C[a[j]]] = a[j];
    }
    for (int j = 0; j < n; j++){
        a[j] = temp[j];
    }
    delete [] C;
    delete [] temp;
}