流离之人追逐幻影

用户名：pwj666

访问量：60259

签　名：

不想总是要失去后才懂得珍惜

等　　级
排　　名	37
经　　验	13962
参赛次数	11
文章发表	110
年　　龄	23
在职情况	在职
学　　校
专　　业

　　自我简介：

TA的其他文章

【原理、题解、代码】最大公约数与最小公倍数
浏览：188

你可能喜欢

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

sort（cmp实现）+选择+冒泡+插入+图解-----每日PAT

　　作者: 流离之人追逐幻影　　　　发表时间：2019-06-21 01:06:33 浏览：477　|　评论：0　

排序基础算法之一，属于常见题型。下面说明一下常见的排序算法，看上哪个就用吧！

------------

**选择排序：**
```
文字描述：对一个序列A中的元素A[1]~A[n],令i从1到n枚举，进行n趟操作，每趟从待排序部分【i,n】中选择最小的元素，令其与待排序部分的第一个元素A[i]进行交换，这样元素A[i]就会与当前有序区间【1,,i-1】形成新的有序区间【1,i】。于是n趟操作后，元素就会是有序的。
```
```
图形描述：
```
![](/image_editor_upload/20190620111752_31743.png)

存储状态：
```
初始序列：{49 27 65 97 76 12 38}
　　第1趟：12与49交换：12{27 65 97 76 49 38}
　　第2趟：27不动　：12 27{65 97 76 49 38}
　　第3趟：65与38交换：12 27 38{97 76 49 65}
　　第4趟：97与49交换：12 27 38 49{76 97 65}
　　第5趟：76与65交换：12 27 38 49 65{97 76}
　　第6趟：97与76交换：12 27 38 49 65 76 97 
  完成
```

C代码：
```
void SelectSort(RecordType r[], int length)　/*对记录数组r做简单选择排序，length为待排序记录的个数*/
{
    int temp;
    for ( i=0 ; i< length-1 ; i++) //n-1趟排序
    {
        int index=i；　//假设index处对应的数组元素是最小的
        for (int j=i+1 ; j < length ; j++) 　//查找最小记录的位置
            if (r[j].key < r[index].key )
                index=j;
        if ( index!=i) 　//若无序区第一个元素不是无序区中最小元素，则进行交换
        {
            temp     = r[i];
            r[i]     = r[index];
            r[index] = temp;
        }
    }
}
```

复杂度：
```
O(n^2)  
```

------------
**冒泡排序：**
```
文字描述：它是一种较简单的排序算法。它会遍历若干次要排序的数列，每次遍历时，它都会从前往后依次的比较相邻两个数的大小；如果前者比后者大，则交换它们的位置。这样，一次遍历之后，最大的元素就在数列的末尾！ 采用相同的方法再次遍历时，第二大的元素就被排列在最大元素之前。重复此操作，直到整个数列都有序为止！
```
```
基本原理：
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素做同样的工作，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
```
```
图片描述：
```
![](/image_editor_upload/20190621120704_48498.png)
C代码:
```
void bubbleSort (elemType arr[], int len) {
    elemType temp;
    int i, j;
    for (i=0; i<len-1; i++) //外循环为排序趟数，len个数进行len-1趟 
        for (j=0; j<len-1-i; j++) { // 内循环为每趟比较的次数，第i趟比较len-i次 
            if (arr[j] > arr[j+1]) { // 相邻元素比较，若逆序则交换(升序为左大于右，降序反之)
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
}
```
算法复杂度：
```
O(N^2)
```

------------

**直接插入排序：**
```
文字描述过程：
第1趟插入：将第2个元素插入前面的有序子序列，此时前面只有一个元素，当然是有序的
第2趟比较：将第3个元素插入前面的有序子序列，前面的2个元素是有序的
......
第n-1趟比较：将第n个元素插入前面的有序子序列，前面n-1个元素是有序的

```

```
图片描述（第一种）：
```
![](/image_editor_upload/20190620114317_88800.png)
```
图片描述（第二种）：
```
![](/image_editor_upload/20190620114811_14414.png)

java代码：
```
public static void insertionSort(int[] nums) {
    int temp;
    for(int i = 1; i < nums.length; i++) {
        for(int j = i - 1; j >= 0 && nums[j] > nums[j + 1]; j--) {
            temp = nums[j];
            nums[j] = nums[j + 1];
            nums[j + 1] = temp;
        }
    }
}
```
复杂度：
```
O(n^2)  
```

优化：
```
上面的算法的缺点：在第i-1趟插入时，需要把第i个元素插入到前面的i-1个元素中，该算法总是从i-1个元素开始逐个比较之前的每个元素，直到找到第i个元素的插入位置，这显然没有利用前面0~i-1个元素已经有序的特点。

优化：在0~i-1个有序元素给第i个元素寻找插入的位置时，使用二分查找法可以有效提高查找插入位置的时间效率，经过优化的插入排序称为折半插入排序
```

------------

**折半插入排序：**

Java代码：
```
public static void binaryInsertionSort(int[] nums) {
    for(int i = 1; i < nums.length; i++) {
        int left = 0;
        int right = i - 1;
        int temp = nums[i];
        // 通过二分查找找到插入的位置
        while(left <= right) {
            int mid = (left + right) / 2;
            if(temp > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // 插入位置之后的元素依次向后移动
        for(int j = i; j > left; j--) {
            nums[j] = nums[j - 1];
        }
        // 更新插入位置的值
        nums[left] = temp;
    }
}
```

------------

**由于排序题中大部分都只需要得到排序的最终结果，而不需要写排序的完整过程（例如冒泡排序，快速排序等过程）因此比赛时强烈建议使用C语言中的库函数qsort或是C++中的sort函数，接下来主讲更简洁的sort函数**
1.如何使用sort排序
```
1.函数的使用必须加上头文件#include<algorithm> 和using namespace std;
2.sort(首元素地址（必填），尾元素地址的下一个地址（必填），比较函数（非必填）)
3.通常是sort(a,a+len,cmp())
不写比较函数的话，默认从小到大排序
4.通常与vector容器配合使用（想了解的请点击如下链接）
```
参考：[1044题-[编程拓展]三个字符串的排序-题解(STL---vector+sort)](https://blog.dotcpp.com/a/60270 "1044题-[编程拓展]三个字符串的排序-题解(STL---vector+sort)")

2.cmp()实现
（1）从大到小
```
bool cmp(int a,int b){
	return a>b;
}
```
（2）结构体数组从小到大（一级排序）
```
struct node{
	int x;
}；
bool cmp(node a,node b){
	return a.x<b.x;
}
```
（3）结构体数组，先按x从小到大,若x相等,则按y从大到小（二级排序）
```
struct node{
	int x;
	int y;
}；
bool cmp(node a,node b){
	if(a.x!=b.x) return a.x<b.x;
	else return a.y>b.y;
}
```
（4）结构体里的字符数组，先按x（字典序）从小到大,若x相等,则按y（字典序）从大到小（二级排序）
```
struct node{
	char x[100];
	char y[100];
}；
bool cmp(node a,node b){
	if(a.x!=b.x) return strcmp(a.x,b.x)<0;
	else return strcmp(a.y,b.y)>0;
}
```

=================还有很多排序 TT==================

2019-06-21 补充了一个结构体里的字符数组的（字典序）比较
===============有时间继续研究更新==================

写了很久，赠人玫瑰，手有余香。点个赞吧。^-^

0.0分

3 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C++代码）

C二级辅导-阶乘数列（C++代码）

C二级辅导-计负均正（C语言代码）

sort（cmp实现）+选择+冒泡+插入+图解-----每日PAT

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言训练-角谷猜想（C++代码）（3N+1问题）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

九宫重排（C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

输出正反三角形（C语言代码）

IP判断（C语言代码）

1392题解(大数相加)

流离之人追逐幻影

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C++代码）

C二级辅导-阶乘数列 （C++代码）

C二级辅导-计负均正 （C语言代码）

sort（cmp实现）+选择+冒泡+插入+图解-----每日PAT

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言训练-角谷猜想 （C++代码）（3N+1问题）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

九宫重排 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

输出正反三角形 （C语言代码）

IP判断 （C语言代码）

1392题解(大数相加)

C二级辅导-阶乘数列（C++代码）

C二级辅导-计负均正（C语言代码）

　　评论区

C语言训练-角谷猜想（C++代码）（3N+1问题）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

九宫重排（C++代码）

输出正反三角形（C语言代码）

IP判断（C语言代码）