快排归并面试算法模版实现

Posted on | In

采用vector和链表两种数据结构实现快排，堆排序，冒泡排序，二分查找等常用算法，vector用模版函数实现，原理网上很多，就不细说了，做了些简单注释。

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <bits/stdc++.h>
using namespace std;

template<typename T>
void swap1(T &a, T &b){
    T temp;
    temp = a;
    a = b;
    b = temp;
}

template<typename T>
void quickSort(vector<T> &vec,int left, int right){
    int low = left, high = right;
    if(vec.size() < 2 || low >= high)
        return;

    T key = low;
    while(low < high){
        //pivot的对立面找一个小于pivot
        while(vec[high] >= vec[key] && high > low)
            high--;
        //从左边找一个大于pivot
        while(vec[low] <= vec[key] && low < high)
            low++;
        //交换
        swap1(vec[low], vec[high]);
    }
    swap1(vec[low], vec[key]);

    //left和right不能变，此时low=high，左右分治递归下去
    quickSort(vec, left, high - 1);
    quickSort(vec, low + 1, right);
}

template<typename T>
void bubbleSort(vector<T> &vec){
    for(int i = vec.size()-1; i >= 0; i--)
        for(int j = 0; j < i; j++)
            if(vec[j] > vec[j+1])
                swap1(vec[j], vec[j+1]);
    return;
}

template<typename T>
void merge(vector<T> &vec, int left, int mid, int right){
    //假设new出来一个空数组在空数组里排序
    vector<T> temp(vec);

    int k = 0;
    int cur1 = left, cur2 = mid+1;

    //令人崩溃的大括号...把这里到return全括住了找了半天
    while(cur1 <= mid && cur2 <= right)
        if(vec[cur1] <= vec[cur2])
            temp[k++] = vec[cur1++];
        else
            temp[k++] = vec[cur2++];
    
    while(cur1 <= mid)
        temp[k++] = vec[cur1++];
    while(cur2 <= right)
        temp[k++] = vec[cur2++];

    //将空数组里的值拷贝回原数组注意考虑到右半边原数组下标需要[left+cur1]
    for (cur1 = 0; cur1 < k; cur1++)
        vec[left + cur1] = temp[cur1];

    return;    

}
template<typename T>
void mergeSort(vector<T> &vec, int left, int right){
    if(left >= right)
        return;
    
    //分解原问题为若干子问题
    int mid = left + (right - left)/2;

    //递归求解子问题，若足够小和直接求得
    mergeSort(vec, left, mid);
    mergeSort(vec, mid+1, right);

    //合并子问题的解
    merge(vec, left, mid, right);
}

template<typename T>
int binarySearch(vector<T> &vec, T key){
    if(vec.size() < 0)
        return -1;
    int low = 0;
    int high = vec.size() - 1;
    int mid = 0;
    //low=high时不能跳出，此时需要进去进行vec[mid]==key判断
    while(low <= high){
        mid = low + (high - low)/2;
        if(vec[mid] == key)
            return mid;
        if(vec[mid] < key)
            low = mid + 1;
        else
            high = mid - 1;
    }
    //没找到返回-1
    return -1;
}

int main(){
    //int a[] = {11,22,33,1,2,5};
    //double a[] = {3.0,6,3.5,4,5,3.2,3,2};
    //int a[] = {80,30,60,40,20,10,50,70};
    //vector<double> vec(a, a+8);

    //vector<double> vec = {3.0,6,3.5,4,5,3.2,3,2};在vs上出错百度是编译器问题

    //vector<int> vec1(vec);
    vector<std::string> vec;
    vec.push_back("lucas");
    vec.push_back("adam");
    vec.push_back("ardark");

    //for(int i = 0; i < 3; i++)
     //   vec.push_back(i);
    //swap1(vec[0], vec[1]);

    mergeSort(vec, 0, vec.size() - 1);
    //quickSort(vec, 0, vec.size() - 1);
    //bubbleSort(vec);
    //int idx = binarySearch(vec, 3.5);
    //cout << "the idx of finding is:" << idx << endl; 
    vector<string>::iterator ite;
    for(ite = vec.begin(); ite < vec.end(); ite++)
        cout << *ite << endl;
}

链表的实现：

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

ListNode* creatListNode(){
    int value;
    cin >> value;
    ListNode* head = new ListNode(value);
    ListNode* rear = head;
    cin >> value;
    while(value){
        ListNode* newNode = new ListNode(value);
        rear->next = newNode;
        rear = newNode;
        cin >> value;
    }
    return head;
}

ListNode *findhalf(ListNode *head){
    ListNode *low = head,*fast = head;
    
    //不能仅判断fast->next->next
    while(fast->next && fast->next->next){
        low=low->next;
        fast=fast->next->next;
    }
    return low;
}
ListNode *mergeSort(ListNode *head){
    //归并排序划分到空或仅有一个节点时,list中是l>=时退出
    if(head==nullptr || head->next==nullptr) return head;
    ListNode* hf = findhalf(head);
    
    ListNode* pb = mergeSort(hf->next);
    //先找右，再断链！！
    hf->next=nullptr;
    ListNode* pa = mergeSort(head);
    return merge(pa,pb);
}
ListNode* merge(ListNode *pa,ListNode *pb){
    ListNode dummy(0);
    ListNode *rear=&dummy;//上面结构体,这里取地址,不是new放在堆栈的临时变量,出括号自动消失
    
    //也不用cur1和cur2来遍历
    while(pa && pb){
        if(pa->val < pb->val) {
            rear->next = pa;
            pa = pa->next;
        }
        else{
            rear->next = pb;
            pb = pb->next;
        }
        rear = rear->next;
    }
    if(pa)
        rear->next = pa;
    if(pb)
        rear->next = pb;
    
    return dummy.next;
}

ListNode *insertionSortList(ListNode *head) {
    if(head == NULL || head->next == NULL) return head;
    ListNode* origin = new ListNode(-1);//也可静态构造
    origin->next = head;
    ListNode *cur1 = origin, *cur2 = head->next, *post = NULL;
    head->next = NULL;
    while (cur2) {
        post = cur2->next;
        cur1 = origin;
        while (cur1->next != NULL && cur1->next->val <= cur2->val) {
            cur1 = cur1->next;
        }
        cur2->next = cur1->next;
        cur1->next = cur2;
        cur2 = post;
    }
    return origin->next;
}

int main(){
    //输入3,4,8,7,9,1,2,0(遇0退出)
    ListNode *head = creatListNode();
    printList(head);
    mergeSort(head);
    printList(head);
    return 0;
}