Stack

1
2

void bubbleSort(vector<int>& array) {
}

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

void insertSortint partition(vector<int>& array) {
	, int len = array.size();
	if (len <= 0) return;

	for (int i = 1; i < len; i++ft, int right) {
		int targepivot = array[iright];
		int j = il = left, r;
		while (j > 0 && array[j-1] > target) {
		array[j] = array[j-1];
			j--;
		}
		array[j] = target;
	}
}

 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

    int partition(vector<int>& nums, int l, int r) {
        int pivot = nums[r];
        int i = l;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                swap(nums[i], nums[j]);
                i = i + 1;
            }
        }
        swap(nums[i], nums[r]);
        return i;
    }

   int randomized_partition(vector<int>& nums, int l, int r) {
        int i = rand() % (r - l + 1) + l; // 随机选一个作为我们的主元
        swap(nums[r], nums[i]);
        return partition(nums, l, r);
    }

   void quicksort(vector<int>& nums, int l, int r) {
        if (l < r) {
            int pos = randomized_partition(nums, l, r);
            quicksort(nums, l, pos - 1);
            quicksort(nums, pos + 1, r);
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        srand((unsigned)time(NULL));
        quicksort(nums, 0, (int)nums.size() - 1);
        return nums;
    }

 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 merge(vector<int>& array, int left, int mid, int right) {
	int i = left, j = mid+1;
	vector<int> result;
	while (i <= mid && j <= right) {
		if (array[i] < array[j]) {
			result.push_back(array[i++]);
		} else {
			result.push_back(array[j++]);
		}
	}
	while (i <= mid) result.push_back(array[i++]);
	while (j <= right) result.push_back(array[j++]);

	copy(result.begin(), result.end(), array.begin()+left);
}

void mergeSort(vector<int>& array, int left, int right) {
	if (left >= right) return;

	int mid = (left + right) / 2;
	mergeSort(array, left, mid);
	mergeSort(array, mid+1, right);
	merge(array, 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

int partition(vector<int>& array, int l, int r) {
	int pivot = array[r];
	int i = l;
	for (int j = l; j <= r-1; j++) {
		if (array[j] <= pivot) {
			swap(array[i], array[j]);
			i++;
		}
	}
	swap(array[i], array[r]);
	return i;
}

int kthSmallest(vector<int>& array, int l, int r, int k) {
	if (k > 0 && k <= r-l+1) {
		int index = partition(array, l, r);
		if (index-l+1 == k) return array[index];
		if (index-l+1 > k) return kthSmallest(array, l, index-1, k);
		return kthSmallest(array, index+1, r, k-index+l-1);
	}
	return INT_MAX;
}

 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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        return MergeSort(head);
    }

    ListNode* MergeSort(ListNode* head) {
        if (head == nullptr || head->next == nullptr) return head;

        ListNode* p1 = head;
        ListNode* p2 = head->next;

        while (p2 && p2->next) {
            p1 = p1->next;
            p2 = p2->next->next;
        }

        ListNode* h1 = head;
        ListNode* h2 = p1->next;
        p1->next = nullptr;

        ListNode* t1 = MergeSort(h1);
        ListNode* t2 = MergeSort(h2);
        return Merge(t1, t2);
    }

    ListNode* Merge(ListNode* p, ListNode* q) {
        ListNode* pre = new ListNode(-1);
        ListNode* cur = pre;

        while (p && q) {
            if (p->val <= q->val) {
                ListNode* tmp = p->next;
                cur->next = p;
                cur = cur->next;
                p = tmp;
            } else {
                ListNode* tmp = q->next;
                cur->next = q;
                cur = cur->next;
                q = tmp;
            }
        }

        if (p) cur->next = p;
        if (q) cur->next = q;

        return pre->next;
    }
};