排序算法(基于c++)

直接插入排序

#include
using namespace std;
void InsertSort(int arr[],int n){
    int temp;
    int i,k;
    for(i=1;i<n;i++){
        temp=arr[i];
        for( k=i-1;k>=0&&arr[k]>temp;k--){
            arr[k+1]=arr[k];

        }
        arr[k+1]=temp;
    }
}

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

希尔排序

//希尔排序
void shellSort(int a[], int n){
    int gap = n / 2;
    while(gap > 0){
        for(int i = gap; i < n; i++){
            int temp = a[i];
            int j = i - gap;
            while(j >= 0 && a[j] > temp){
                a[j + gap] = a[j];
                j -= gap;
            }
            a[j + gap] = temp;
        }
        gap /= 2;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

快速排序

//快速排序
void quickSort(int a[], int left, int right){
    if(left >= right){
        return;
    }
    int i = left;
    int j = right;
    int key = a[left];
    while(i < j){
        while(i < j && a[j] >= key){
            j--;
        }
        a[i] = a[j];
        while(i < j && a[i] <= key){
            i++;
        }
        a[j] = a[i];
    }
    a[i] = key;
    quickSort(a, left, i - 1);
    quickSort(a, i + 1, right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

简单选择

//简单选择排序
void selectSort(int a[], int n){
    for(int i = 0; i < n; i++){
        int min = i;
        for(int j = i + 1; j < n; j++){
            if(a[j] < a[min]){
                min = j;
            }
        }
        if(min != i){
            int temp = a[i];
            a[i] = a[min];
            a[min] = temp;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

堆排序

//堆排序
void heapAdjust(int a[], int i, int n){
    int child = 2 * i + 1;
    while(child < n){
        if(child + 1 < n && a[child] < a[child + 1]){
            child++;
        }
        if(a[i] < a[child]){
            int temp = a[i];
            a[i] = a[child];
            a[child] = temp;
            i = child;
            child = 2 * i + 1;
        }else{
            break;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

二路归并排序

//二路归并排序递归
void merge(int a[], int left, int mid, int right){
    int *temp = new int[right - left + 1];
    int i = left;
    int j = mid + 1;
    int k = 0;
    while(i <= mid && j <= right){
        if(a[i] < a[j]){
            temp[k++] = a[i++];
        }else{
            temp[k++] = a[j++];
        }
    }
    while(i <= mid){
        temp[k++] = a[i++];
    }
    while(j <= right){
        temp[k++] = a[j++];
    }
    for(int i = 0; i < k; i++){
        a[left + i] = temp[i];
    }
    delete[] temp;
}
    
        
    void mergeSort(int a[], int left, int right){
    if(left >= right){
        return;
    }
    int mid = (left + right) / 2;
    mergeSort(a, left, mid);
    mergeSort(a, mid + 1, right);
    merge(a, left, mid, right);
}
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

基数排序

//基数排序
void radixSort(int a[], int n){
    int max = a[0];
    for(int i = 1; i < n; i++){
        if(a[i] > max){
            max = a[i];
        }
    }
    int d = 1;
    int *temp = new int[n];
    while(max / d > 0){
        int count[10] = {0};
        for(int i = 0; i < n; i++){
            int k = (a[i] / d) % 10;
            count[k]++;
        }
        for(int i = 1; i < 10; i++){
            count[i] += count[i - 1];
        }
        for(int i = n - 1; i >= 0; i--){
            int k = (a[i] / d) % 10;
            temp[count[k] - 1] = a[i];
            count[k]--;
        }
        for(int i = 0; i < n; i++){
            a[i] = temp[i];
        }
        d *= 10;
    }
    delete[] temp;
}
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