基本的排序算法-选择、插入、冒泡、希尔、归并、堆、快速

Posted on   |   In

如题，排序算法是尝尝会被问及的，那么记录下来方便以后访问吧！
先定义个数组，然后写好交换和显示所有元素的函数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lst[] = {1,4,2,3,4,5,3,4,6,8,7,9,6};
void Swap(int x[],int i,int j){
    int tem = x[i];
    x[i] = x[j];
    x[j] = tem;
}
void print(int x[],int length){
    for(int i = 0; i < length; i++){
        cout << x[i] << "\t";
    }
    cout <<endl;
}

好了，开工，按难度开始吧！
<—————————–冒泡排序—————————->

1
2
3
4
5
6
7
8
9
10
11
12
void bubbleSort(int r[],int length){
    bool flag = true;
    for(int i = 0; i < length-1 && flag; i++){
        flag = false;
        for(int j = 0; j < length - i-1;j++){
            if(r[j] < r[j+1]) {
                Swap(r,j,j+1);
                flag = true;
            }
        }
    }
}

<—————————–选择排序—————————->

1
2
3
4
5
6
7
8
9
void selectSort(int r[],int length){
    for(int i = 0; i < length-1; i++){
        int _min = i;
        for(int j = i+1; j < length; j ++){
            if(r[j] < r[_min]) _min = j;
        }
        Swap(r,_min,i);
    }
}

<—————————–插入排序—————————->

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void insertSort(int r[],int length){
    int _trans = 0;
    for(int i = 0; i < length - 1; i++){
        if(r[i] > r[i+1]){
            _trans = r[i+1];
            int k = i;
            while(r[k] > _trans && k >= 0){//这里是为了防止r[k]乱值导致错误k的索引
                r[k+1] = r[k];
                k--;
            }
            r[k+1] = _trans;
        }
    }
}

<—————————–希尔排序—————————->

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void shellSort(int r[],int length){
    int increment = length/2;
    while(increment >= 1){
        for(int i = increment; i < length ; i++){
            int j = i-increment;
            int key = r[i];
            while(j >=0 && r[j] > key){
                    r[j+increment] = r[j];
                    j = j-increment;
            }
            r[j+increment] = key;
        }
        increment = increment/2;
    }
}

<—————————–快速排序—————————->

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

<—————————–建堆排序—————————->

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
void maxHeapify(int r[],int heapSize,int index){
    int left = 2*index+1;
    int right = 2*index+2;
    int larger = index;
    if(r[larger] < r[left] && left <= heapSize) {//不能有left=heapSize
        larger = left;
    }else larger = index;
    if(r[larger] < r[right] && right <= heapSize){//不能有left=heapSize
        larger = right;
    }
    if(larger!=index){
        Swap(r,larger,index);
        maxHeapify(r,heapSize,larger);
    }
}
int lastNode(int index){
    if(index/2==0) return (index-1)/2;
    else return (index-2)/2;
}
void buildMaxHeap(int r[],int heapSize){
    for(int i = lastNode(heapSize); i >= 0; i --){
        maxHeapify(r,heapSize,i);
    }
}
void heapSort(int r[],int length){
    int heapSize = length;
//    buildMaxHeap(r,length);
    print(r,heapSize);
    for(int i = heapSize - 1; i > 0; i--){
        Swap(r,0,heapSize-1);
        heapSize--;
        print(r,heapSize);
        maxHeapify(r,heapSize,0);
    }
}

<—————–恭喜大家掌握了基本的排序算法——————>