数据结构----直接选择排序C++代码

我会带着你远行 2022-04-03 06:47 193阅读 0赞

*  ### 插入排序的基本思想是：每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。 ###

## ##

*  ### 直接插入排序是一种最简单的排序方法，其基本操作是将一条记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。 ###

## ##

*  ### 算法步骤： ###

### 首先在当前有序区R\[1..i-1\]中查找R\[i\]的正确插入位置k(1≤k≤i-1)；然后将R\[k．．i-1\]中的记录均后移一个位置，腾出k位置上的空间插入R\[i\]。 ###

### 注意：若R\[i\]的关键字大于等于R\[1．．i-1\]中所有记录的关键字，则R\[i\]就是插入原位置。 ###

## ##

*  ### 算法中引进的附加记录R\[0\]称监视哨或哨兵(Sentinel)。 ###

### 哨兵有两个作用： ###

### ① 进人查找(插入位置)循环之前，它保存了R\[i\]的副本，使不致于因记录后移而丢失R\[i\]的内容； ###

### ② 它的主要作用是：在查找循环中"监视"下标变量j是否越界。一旦越界(即j=0)，因为R\[0\].可以和自己比较，循环判定条件不成立使得查找循环结束，从而避免了在该循环内的每一次均要检测j是否越界(即省略了循环判定条件"j>=1")。 ###

**注意：**

**① 实际上，一切为简化边界条件而引入的附加结点(元素)均可称为哨兵。**

**【例】单链表中的头结点实际上是一个哨兵**

**② 引入哨兵后使得测试查找循环条件的时间大约减少了一半，所以对于记录数较大的文件节约的时间就相当可观。对于类似于排序这样使用频率非常高的算法，要尽可能地减少其运行时间。所以不能把上述算法中的哨兵视为雕虫小技，而应该深刻理解并掌握这种技巧。**

### 以下是直接插入排序C++正确源代码： ###

#include<iostream>
    #include<stdio.h>
    using namespace std;
    
    //直接插入排序 C++ 实现 
    #define MAXSIZE 100
    typedef int  KeyType;
    typedef int InfoType;
    typedef struct
    {
    	KeyType key;
    	InfoType otherinfo;
    }RedType;
    
    typedef struct
    {
    	RedType r[MAXSIZE+1];	//r[0] 闲置或做哨兵单元
    	int length; 
    }SqList;
    
    void InsertSort(SqList &L)
    {
    	for(int i=2;i<=L.length;i++)
    		if(L.r[i].key<L.r[i-1].key)
    		{
    			L.r[0]=L.r[i];	//将待插入的记录暂存在监视哨中 
    			L.r[i]=L.r[i-1];	//r[i-1]后移
    			int j;
    			for(j=i-2;L.r[0].key<L.r[j].key;--j) //从后向前寻找插入位置 
    			L.r[j+1]=L.r[j];	//记录逐个后移，直到找到插入位置
    			L.r[j+1]=L.r[0];	//将r[0]即原r[i],插入正确位置 
    		}
    }
    
    int main()
    {
    	SqList L;
    	int n;
    	cout<<"请输入记录的个数：";
    	cout<<endl;
    	cin>>n;
    	for(int i=1;i<=n;i++)
    		cin>>L.r[i].key;
    	L.length=n;
    	for(int i=1;i<=L.length;i++)
    		cout<<L.r[i].key<<"  ";
    		cout<<endl;
    	InsertSort(L);
    	for(int i=1;i<=L.length;i++)
    		cout<<L.r[i].key<<"  ";
    		cout<<endl;
    	return 0;
    }

*  ### 直接选择排序算法特点： ###

**（1）稳定排序（有的版本认为是不稳定排序，这里是按照严蔚敏《数据结构》）。**

**（2）算法简单，且容易实现。**

**（3）也适用于链式存储结构，只是在单链表上无需移动记录，只需要修改指针。**

**（4）更适合于初始记录有序（正序）的情况，当初始记录无序，n 比较大时，此算法时间复杂度较高，不宜采用。**

*  **时间复杂度为  O（n\*n）;空间复杂度为 O（1）。**