快速排序（快拍）

快速排序的思想是分治，平均时间复杂度O(nlogn)，当然快速排序的时间复杂度并不是稳定的，最大时间复杂度是n^2。当然在用C语言实现的快速排序中，快速排序是原地排序，所有排序中空间复杂最低。

代码

基于数组的快速排序（递归） 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void qSort(int *a, int low, int high){
    if(low > high) return;
    int first = low;
    int last = high;
    int key = a[first];
    while(first < last){
        while(first < last && a[last] >= key) --last;
        if(first < last) a[first] = a[last]; //这个地方是精髓啊
        while(first < last && a[first] <= key) ++first;
        if(first < last) a[last] = a[first];
        }
    a[first] = key;
    Qsort(a, low, first-1);
    Qsort(a, first+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
void swap(int *x, int *y) {
    int t = *x;
    *x = *y;
    *y = t;
}
void quick_sort_recursive(int arr[], int start, int end) {
    if (start >= end)
        return;
    int mid = arr[end];
    int left = start, right = end - 1;
    while (left < right) {
        while (arr[left] < mid && left < right)
            left++;
        while (arr[right] >= mid && left < right)
            right--;
        swap(&arr[left], &arr[right]);
    }
    if (arr[left] >= arr[end])
        swap(&arr[left], &arr[end]);
    else
        left++;
    if (left)
        quick_sort_recursive(arr, start, left - 1);
    quick_sort_recursive(arr, left + 1, end);
}
void quick_sort(int arr[], int len) {
    quick_sort_recursive(arr, 0, len - 1);
}

php的快速排序

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
function qSort(&$envelopes, $start, $end )
{
        if($end <= $start)
        {
            return;
        }
        $i = $start;
        $j = $end;
        while($i < $j)
        {
            while($i < $end && $envelopes[$i] <= $envelopes[$start])
            {
                $i++;
            }
            while($j > $start && $envelopes[$j] >  $envelopes[$start])
            {
                $j--;
            }
            if($i < $j)
            {
                $tmp = $envelopes[$i];
                $envelopes[$i] = $envelopes[$j];
                $envelopes[$j] = $tmp;
            }
        }
        //或者当i= 8 j = 10 i--j++（处理当j==i ）指向9事无法交换情况。
        if($envelopes[$i] < $envelopes[$start]) {
            $tmp = $envelopes[$start];
            $envelopes[$start] = $envelopes[$j];
            $envelopes[$i] = $tmp;
        }
        qSort($envelopes, $start, $i-1);
        qSort($envelopes, $i+1, $end);
}

基于链表的快速排序

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
struct Node   
{  
    int key;  
    Node* next;  
};  
  
void swap(int* a, int* b)
{
    int tmp = *a ;
    *a = *b;
    *b = tmp;
}  
Node* GetPartion(Node* pBegin, Node* pEnd)  
{  
    int key = pBegin->key;  
    Node* p = pBegin;  
    Node* q = p->next;  
  
    while(q != pEnd)  
    {  
        if(q->key < key)  
        {  
            p = p->next;  
            swap(p->key,q->key);  
        }  
  
        q = q->next;  
    }  
    swap(&p->key,&pBegin->key);  
    return p;  
}  
  
void QuickSort(Node* pBeign, Node* pEnd)  
{  
    if(pBeign != pEnd)  
    {  
        Node* partion = GetPartion(pBeign,pEnd);  
        QuickSort(pBeign,partion);  
        QuickSort(partion->next,pEnd);  
    }  
}

并归排序

并归排序的思想是分治的思想，时间复杂度 O(nlogn)。

  • 如果一个链表（数组）只有一个元素或者为空直接返回。
  • 如果链表（数组）可以分成尽可能相等两部分，将其分成尽可能相等两部分。
  • 对于两个被分开的两个部分进行整个归并排序
  • 把两个拍好序的链表（数组）进行合并。
    与快拍的区别是：快排是先处理完再递归 而归并排序是先递归在处理

基于链表的并归排序。

代码

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
 struct ListNode * merge(struct ListNode *l1,struct ListNode *l2)
 {
     if(l1 == NULL) return l2;
     if(l2 == NULL) return l1;
     if( (l1==NULL) &&(l2==NULL) ) return NULL;
     
     struct ListNode *head=NULL;
     if(l1->val < l2->val)
    {
        head=l1;
        l1=l1->next;
    }
     else 
     {
         head=l2;
         l2=l2->next;
     }
     
     struct ListNode *p=head;
     while(l1 != NULL && l2 != NULL)
     {
         if(l1->val < l2->val)
         {
             p->next=l1;
             l1=l1->next;
         }
         else
         {
             p->next=l2;
             l2=l2->next;
         }
         p=p->next;
     }
     
     if(l1 != NULL) p->next=l1;
     if(l2 != NULL) p->next=l2;
     return head;
 }
 
struct ListNode* sortList(struct ListNode* head) {
    if(head == NULL || head->next == NULL) return head;
    struct ListNode *slow=head;
    struct ListNode *fast=head;
    struct ListNode *pre=NULL;
    
    // 切成两半
    while(fast!= NULL && fast->next != NULL)
    {
        pre=slow;
        slow=slow->next;
        fast=fast->next->next;
    }
    pre->next=NULL;
    
    //两半分别归并
    struct ListNode *l1=sortList(head);
    struct ListNode *l2=sortList(slow);
    
    //调用merge
    return merge(l1,l2);
}

基于数组的并归排序(递归)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void merge_sort_recursive(int arr[], int reg[], int start, int end) {
    if (start >= end)
        return;
    int len = end - start, mid = (len >> 1) + start;
    int start1 = start, end1 = mid;
    int start2 = mid + 1, end2 = end;
    merge_sort_recursive(arr, reg, start1, end1);
    merge_sort_recursive(arr, reg, start2, end2);
    int k = start;
    while (start1 <= end1 && start2 <= end2)
        reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
    while (start1 <= end1)
        reg[k++] = arr[start1++];
    while (start2 <= end2)
        reg[k++] = arr[start2++];
    for (k = start; k <= end; k++)
        arr[k] = reg[k];
}
void merge_sort(int arr[], const int len) {
    int reg[len];
    merge_sort_recursive(arr, reg, 0, len - 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
int min(int x, int y) {
    return x < y ? x : y;
}
void merge_sort(int arr[], int len) {
    int* a = arr;
    int* b = (int*) malloc(len * sizeof(int));
    int seg, start;
    for (seg = 1; seg < len; seg += seg) {
        for (start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int* temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}

冒泡排序

时间复杂度与空间复杂度

时间复杂度O(n^2)

代码

c语言冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void bubbleSort(int *nums, int lenNums) {
int i,j;
int flag = 1;
for(i = 0; i < lenNums; i++)
{
    flag = 0;
    for(j=0; j< lenNums - i -1; j++)
    {
        //比较并交换
        if(nums[j] > nums[j+1])
        {
            nums[j] = nums[j+1] + nums[j];
            nums[j+1] = nums[j] - nums[j+1];
            nums[j] = nums[j] - nums[j+1];
            flag = 0;
        }
    }
    if(flag == 1) 
    {
        break;
    }
}
}

插入排序

时间复杂度与空间复杂度

时间复杂度O(n^2),空间复杂度O(1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
void insertSort(int *nums, int numsLen)
{
    int tmp;
    for(int i = 1; i< numsLen; i++)
    {
        tmp = nums[i];
        for(int j = i; j>0 && nums[j] < nums[j-1]; j--)
        {
            nums[j] = nums[j-1];
        }
        nums[j] = tmp;
    } 
}

基数排序

基数排序是将 需要排序的所有数字统一为固定位数的数字（如果位数不足向前补0），然后按照位数切割，分别对每一个位数进行比较。从最低位开始，依次进行一次排序。这样排完以后就会变成一个有序序列。

时间复杂度与空间复杂度

代码

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
function radixsort($nums)
{
    $maxNum = max($nums);
    $wei = 0;
    for($exp =1 ; intval(($maxNum/$exp ))> 0; $exp*=10 )
    {
    	$nums = countSort($nums,$exp);
    	var_dump($nums);
    }
}
function countSort($nums,$exp)
{
	for ($i=0; $i < 10; $i++) { 
		$count[$i] = 0;
	}
    for($i = 0; $i< count($nums); $i++)
    {
    	$key = intval(($nums[$i]/$exp)%10);
    	$count[intval(($nums[$i]/$exp)%10)]++;
    }
    for($i = 1; $i < 10; $i++)
    {
    	$count[$i] += $count[$i - 1];
    }
    for($i = count($nums)-1; $i >= 0; $i--)
    {
    	$output[$count[intval(($nums[$i]/$exp)%10) ] -1] = $nums[$i];
    	$count[intval((($nums[$i]/$exp)%10))]--;
    }
    for ($i=0; $i < count($nums) ; $i++) { 
    	$nums[$i] = $output[$i];
    }
    return $nums;
}
$a = [1,3,4,5,12,412,534,122];
radixsort($a);

堆排序

以最大堆为例，最大堆就是一个特殊二叉树，父节点大于子节点。
当前算法是以层序遍历，将二叉树存入数组中。

  • 堆排序每次把处于堆顶的最大值取出
  • 然后对堆进行排序
  • 一次循环，直至堆变为0
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
<?php
// echo number_format(100000.5)."\n";
// echo number_format("100000.5",2)."\n";
// echo number_format(100000.5,1,".","");
function heapSort($nums)
{
    //将数组划转为堆(依赖数组实现的堆)
    $n = count($nums);
    for($i = intval($n/2) -1 ; $i >= 0; $i--)
    {
        heapify($nums, $n, $i);
    }
    for($i = $n-1; $i >= 0; $i--)
    {
    	$tmp = $nums[0];
    	$nums[0] = $nums[$i] ;
    	$nums[$i] = $tmp;
    	heapify($nums, $i, 0);
    }
    var_dump($nums);
}
function heapify(&$nums, $n, $i)
{
    $largest = $i;
    $l = $i * 2 +1;
    $r = $i * 2 +2;
    if($l < $n && $nums[$largest] < $nums[$l])
    {
    	$largest = $l;
    }
    if($r < $n && $nums[$largest] < $nums[$r])
    {
    	$largest = $r;
    }
    if($largest != $i)
    {
    	$tmp = $nums[$i];
    	$nums[$i] = $nums[$largest];
    	$nums[$largest] = $tmp;
    	heapify($nums, $n, $largest);
    }
}
$a = [1,3,4,5,12,412,534,122,534,0,77,88,99,78,56,35,34,1];
heapSort($a);
}

桶排序

1