排序算法

冒泡排序

正序：将最大的不断交换到序列末尾

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void Bubble_sort(vector<int> &nums){
    int n = nums.size();
    bool flag = 0;
    for(int i = 0;i<n-1;i++){
        flag = 0;
        for(int j = 0;j<n-i-1;j++){
            if(nums[j]>nums[j+1]){
                // swap(nums[j],nums[j+1]);
                int t = nums[j];
                nums[j] = nums[j+1];
                nums[j+1] = t;
                flag= 1;
            }
        }
        // 优化:有序后直接，排序结束
        if(flag == 0) break;
        
    }
}

选择排序

每一次选择最大的/最小的到最新有序序列末尾

1
2
3
4
5
6
7
8
9
10
11
12
void select_sort(vector<int> &nums){
      int n = nums.size();
      for(int i = 0;i<n;i++){
          for(int j = i+1;j<n;j++){
              if(nums[j]>nums[i]){
                  int t = nums[i];
                  nums[i] = nums[j];
                  nums[j] = t; 
              }
          }
      }
  }

插入排序

将有序序列的下一个数字插入到有序数列中

1
2
3
4
5
6
7
8
9
10
11
12
13
void insert_sort(vector<int> &nums){
    for(int i = 1;i<nums.size();i++){
        int key = nums[i];
        int j = i-1;
        while (j>=0 && nums[j]>key)
        {
            /* code */
            nums[j+1] = nums[j];
            j--;
        }
        nums[j+1] = key;
    }
}

快速排序

子问题：荷兰国旗问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 void quick_sort(vector<int> &nums,int l,int r){
        // 定基准
        const int pivot = nums[l+(rand()%(r-l))];
		int j,k,i;
// partion
		i = l;
		j = l;
		k = r;
        while (i<k)
        {
            if(nums[i]<pivot){
				swap(nums[i++],nums[j++]);
			}
			else if(nums[i]>pivot){
				swap(nums[--k],nums[i]);
			}else{
				i++;
			}
        }
		quick_sort(nums,l,i);
		quick_sort(nums,k,r);
        
    }

归并排序

两个步骤

1、左右连部分各自排序

2、左右部分合并到一起

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
  
void merge_sort(vector<int> &nums,int l,int r){
    if (l>=r) return ;
    int mid = l+((r-l)>>1);
    // 分
    int l1 = l,r1 = mid;
    int l2 = mid+1,r2 = r;
    merge_sort(nums,l1,r1);
    merge_sort(nums,l2,r2);
    // 合
    vector<int> temp;
    int k = l;
    // 比较
    while (l1<=r1 && l2<=r2)
    {
        /* code */
        if(nums[l1]<nums[l2]){
            temp.push_back(nums[l1++]);
        }else{
            temp.push_back(nums[l2++]);
        }
    }
    while (l1<=r1)
    {
        temp.push_back(nums[l1++]);
    }
    while (l2<=r2)
    {
        temp.push_back(nums[l2++]);
    }
    
    for(int i = l;i<=r;i++){
        nums[i] = temp[i-l];
        // temp.pop_back();
			
    }
}