十大经典排序

main函数

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
int main()
{
	int n;
	while (cin >> n)
	{
		vector<int> nums;
		nums.clear();
		for (int i = 0; i < n; i++)
		{
			int x;
			cin >> x;
			nums.push_back(x);
		}
		//nums = BubbleSort(nums);
		//nums = SelectionSort(nums);
		//nums = InsertionSort(nums);
	   //QuickSort(nums, 0, nums.size()-1);
		//nums = MergeSort(nums, 0, nums.size() - 1);
		nums = ShellSort(nums);
		for (int i = 0; i < n; i++)
		{
			printf("%d%c", nums[i], i == n - 1 ? '\n' : ' ');
		}
	}
}

冒泡排序。

• 冒泡排序维基百科
• 简单描述：（降序）从序列中第一个数开始，相邻数比较，a[j]<a[j+1]就交换，换下来最后一个就是最小值，以此类推。
• code

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  // 冒泡排序
  vector<int> BubbleSort(vector<int>& nums)
  {
    int len = nums.size();
    for (int i = 0; i < len - 1; i++)
    {
        for (int j = 0; j < len - 1 - i; j++)
        {
            if (nums[j] < nums[j + 1])
                swap(nums[j], nums[j + 1]);
        }
    }
    return nums;
  }
  

  选择排序

• 维基百科
• 简单描述：（降序）从序列第一个数开始，找该数向后的最大值并记录下表，最后交换，第一个数就成为最大值，以此类推。
• code

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  // 选择排序
  vector<int> SelectionSort(vector<int>& nums)
  {
    int len = nums.size();
    for (int i = 0; i < len - 1; i++)
    {
        int maxPos = i;
        for (int j = i + 1; j < len; j++)
        {
            if (nums[maxPos] < nums[j])
                maxPos = j;
        }
  
        swap(nums[i], nums[maxPos]);
    }
    return nums;
  }
  

  插入排序

• 维基百科
• 简单描述：(升序)默认有一个有序序列，从其它数中找到合适的位置给插进去，维基百科的图一看就懂，见下图。
• code

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  // 插入排序
  vector<int> InsertionSort(vector<int>& nums)
  {
    // 从小到大。
    int len = nums.size();
    for (int i = 1; i < len; i++)
    {
        int key = nums[i]; // 已经拍好序列（升序）的后一位。给Key找合适位置。
        int j = i - 1;
        while (j >= 0 && nums[j] > key)
        {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = key;
    }
    return nums;
  }
  

  希尔排序

• 维基百科
• 简单描述：就是对插入排序进行分治操作，设置步长，对列排序这样然后慢慢减少步长，步长为一就排序完成。这样姿势使序列部分有序从而减少交换次数。 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率。例子:。
• code

  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
  //希尔排序
  vector<int> ShellSort(vector<int>& nums)
  {
    int n = nums.size();
    for (int gap = n / 2; gap > 0; gap /= 2)
        for (int i = gap; i < n; ++i)
        {
            int key = nums[i];
            int j = i-gap;
            while (j >= 0 && nums[j] > key)
            {
                nums[j + gap] = nums[j];
                j -= gap;
            }
        	nums[j + gap] = key;
            /*cout << "gap = " << gap << endl;
            for (int ii = 0; ii < n; ii++)
            {
                if (ii % gap == 0)
                    puts("");
                    printf("%d%c", nums[ii], ii == n - 1 ? '\n' : ' ');
            }*/
        }
    return nums;
  }
  

  归并排序

• 维基百科
• 简单描述：（升序）把数列看成完美二叉树的最底层。然后按照规则一直合并叶节点。如图
• code

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  //归并排序
  vector<int> MergeSort(vector<int>& nums, int start, int end)
  {
    if (start >= end)
        return { nums[start] };
    int mid = start + (end - start) / 2;
    vector<int> lnums = MergeSort(nums, start, mid);
    vector<int> rnums = MergeSort(nums, mid + 1, end);
    vector<int> res;
    int L = 0, R = 0;
    while (L <= mid - start && R <= end - mid - 1)
    {
        if (lnums[L] < rnums[R])
            res.push_back(lnums[L++]);
        else
            res.push_back(rnums[R++]);
    }
    while (L <= mid - start)
        res.push_back(lnums[L++]);
    while (R <= end - mid - 1)
        res.push_back(rnums[R++]);
    return res;
  }
  

  快排

• 维基百科
• 简单描述：（降序）利用分治的思想。在数列中寻找中间值，按规则调换中间值左右数字位置，需要考虑划分的边界问题。过程如图
• code

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  // 快速排序。
  void QuickSort(vector<int>& nums, int start, int end)
  {
    if (start >= end)
        return;
    int mid = nums[end];
    int L = start, R = end - 1;
    while (L < R)
    {
        while (nums[L] < mid && L < R)
            L++;
        while (nums[R] >= mid && L < R)
            R--;
        swap(nums[L], nums[R]);
    }
    if (nums[L] > nums[end])
        swap(nums[L], nums[end]);
    QuickSort(nums, start, L);
    QuickSort(nums, L + 1, end);
  }//部分分治区间重复划分mid值。
  

• 边界问题。后续部分代码可以替换为:

  1
  2
  3
  4
  5
  6
  7
  8
    if (nums[L] >= nums[end])
        swap(nums[L], nums[end]);
    else
    {
        L++;
    }
    QuickSort(nums, left, L - 1);
    QuickSort(nums, L + 1, end);
  

  两种情况：
  1）nums[L] > nums[R] 交换位置。此时左边都是小于mid的值右边都是大于mid的值。mid不用参与再次划分。
  2）nums[L] < nums[R] 此时nums[left]不是基元 （不能保证左边都小于它右边都大于它）mid后面一位则可以作为基元保证这种情况。 ## 桶排序 ## 堆排序 ## 计数排序 ## 基数排序

---

• Previous
  C++指针和地址
• Next
  Mysql

---