【数据结构】什么是内排序、外排序？内排序详细介绍

野性酷女 2023-09-26 10:32 69阅读 0赞

## **目录** ##

一、什么是内排序？什么是外排序？

二、内排序详细介绍

1. 定义

2、排序分类&稳定性

3、内排序的方法

4、排序算法的性能评价

5、待排序记录的类描述

6、算法：顺序表插入

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

## 前言 ##

**排序**是计算机程序设计中的一种重要操作，其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个相知有序的序列。排序分为两类：内排序和外排序。

![0fcb03f19a1d429a925ec592023a1198.png][]

## 一、什么是内排序？什么是外排序？ ##

**内排序：**全称为内部排序。内部排序是指待排序列数据记录**完全存放在内存中**所进行的排序过程，适合不太大的元素序列。

**外部排序：**是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中还需要**访问外部存储器**的排序。

我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。

> **内部排序方法：**  
> 　　1.插入排序（直接插入排序）；  
> 　　2.快速排序；  
> 　　3.选择排序（简单选择排序）；  
> 　　4.归并排序；  
> 　　5.冒泡排序；  
> 　　6.希尔排序；  
> 　　希尔排序是对直接插入排序方法的改进。  
> 　　7.堆排序；

## 二、内排序详细介绍 ##

### 1. 定义 ###

*  排序：将一组**`无序`**的记录序列调整为**`有序`**的记录序列的一种操作。
 *  排序的目的：提高查询的效率。
 *  相关名词：
    
    > 1.关键字：数据元素(或记录)中某个数据项，用于标识该数据元素(或记录)。作为排序依据的数据项。
    > 
    > 2.主关键字：能够唯一标识一条记录的数据项。
    > 
    > 3.次关键字：能表示多条记录的数据项。
 *  排序稳定性：
    
     *  相同的关键字（52、52），通过排序算法排序后，顺序是否相同
        
        > 1.如果相同（52、52），算法是稳定算法
        > 
        > 2.如果不同（52、52），算法是不稳定算法。
        
        ![76563fc45cca48f790999dab731b97e0.png][]
 *  约定：
    
    > 1.排序：按关键字非递增（**从小到大**）排序
    > 
    > 2.存储：以**顺序表**作为排序表的存储结构
    > 
    > 3.类型：关键字类型为**整形**

### 2、排序分类&稳定性 ###

*  按照**`存储器不同`**分为：外部排序、内部排序
    
    >  *  内部排序：所有数据都在**内存中进行的排序**。适合数据量小的数据元素的排序。
    >  *  外部排序：排序过程中，需要**访问外部存储器的排序**。待排序的数据元素非常多必须存储在外部存储器上。
 *  按照`相同关键字排序前后的位置`分为：**稳定排序、不稳定排序**。例如：\{3,4,2,==3==,1\}
    
    >  *  稳定排序：**相同关键字间的前后位置关系在排序前和排序后保持一致**。例如：\{1,2,3,==3==,4\}
    >  *  不稳定排序：**保持不一致**。例如：\{1,2,==3==,3,4\}

### 3、内排序的方法 ###

*  内部排序：一个逐渐扩大记录的有序序列长度的过程。

<table> 
 <thead> 
  <tr> 
   <th style="width:74px;">类型</th> 
   <th style="width:614px;">描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td style="width:74px;">插入类</td> 
   <td style="width:614px;">将无序子序列中的一个或几个记录<span style="color:#fe2c24;"><strong><code>插入</code></strong></span>到有序序列中，从而增加记录的有序子序列的长度。</td> 
  </tr> 
  <tr> 
   <td style="width:74px;">交换类</td> 
   <td style="width:614px;">通过<span style="color:#fe2c24;"><strong><code>交换</code></strong></span>无序序列中的记录，从而得到其中关键字最小或最大的记录，并将它加入到有序 子序列中，以此方法增加记录的有序子序列的长度。</td> 
  </tr> 
  <tr> 
   <td style="width:74px;">选择类</td> 
   <td style="width:614px;">从记录的无序子序列中<span style="color:#fe2c24;"><strong><code>选择</code></strong></span>关键字最小或最大的记录，并将它加入到有序子序列中， 以此方法增加记录的有序子序列的长度。</td> 
  </tr> 
  <tr> 
   <td style="width:74px;">归并类</td> 
   <td style="width:614px;">通过<span style="color:#fe2c24;"><strong><code>归并</code></strong></span>两个或两个以上的记录有序子序列，逐渐增加记录有序序列的长度。</td> 
  </tr> 
 </tbody> 
</table>

### 4、排序算法的性能评价 ###

>  *  排序算法好坏的标准：算法的时间复杂度、算法的空间复杂度
>  *  排序是一个经常使用的运算，**`所需时间`**是衡量排序算法好坏的重要标志。
>  *  排序的时间开销，可以通过算法执行过程中的记录**`比较次数`**和**`移动次数`**来衡量。

### 5、待排序记录的类描述 ###

*  实现内部排序的==基本操作==有两个：
    
    > 1. “比较”序列中两个关键字的大小
    > 
    > 2. “移动”记录
 *  顺序表记录结点类：

/**
     * 顺序表记录结点类
     */
    public class RecordNode {
    
    	public Comparable key; // 关键字
    	public Object element; // 数据元素
    
    	public RecordNode() {
    	}
    
    	public RecordNode(Comparable key) { // 构造方法1
    		this.key = key;
    
    	}
    
    	public RecordNode(Comparable key, Object element) { // 构造方法2
    		this.key = key;
    		this.element = element;
    	}
    
    	public String toString() { // 覆盖toString()方法
    		return "[" + key + "," + element + "]";
    	}
    }

*  带排序的顺序表类描述：

public class SeqList {
    
        public RecordNode[] r;    //顺序表记录结点数组
        public int curlen;        //顺序表长度,即记录个数
        
        // 顺序表的构造方法，构造一个存储空间容量为maxSize的顺序表
        public SeqList(int maxSize) {
            this.r = new RecordNode[maxSize];  // 为顺序表分配maxSize个存储单元
            this.curlen = 0;                   // 置顺序表的当前长度为0
        }
        
        public void display() {    //输出数组元素
            for (int i = 0; i < this.curlen; i++) {
                // 如果是个位数，多输出一个空格
                String str = r[i].key.toString().length() == 1 ? "  " : " ";
                System.out.print(str + r[i].key.toString());
            }
            System.out.println();
        }
        
       public void display(int sortMode) {    //输出数组元素
            int i;
            if(sortMode==9)   //带监视哨的直接插入排序方法，0号单元用于存放监视哨
                i=1;
            else
                i=0;
            for (; i < this.curlen; i++) {
                String str = r[i].key.toString().length() == 1 ? "  " : " ";
                System.out.print(str + r[i].key.toString());
            }
            System.out.println();
        }
        
    }

### 6、算法：顺序表插入 ###

**1、步骤：**

>  *  在当前顺序表的第i个结点之前插入一个RecordNode类型的结点x
>  *  其中i取值范围为：0≤i≤length()。
>  *  如果i值不在此范围则抛出异常,当i=0时表示在表头插入一个数据元素x,
>  *  当i=length()时表示在表尾插入一个数据元素x

**2、代码：**

public void insert(int i, RecordNode x) throws Exception {
            if (curlen == r.length) {    // 判断顺序表是否已满
                throw new Exception("顺序表已满");
            }
            if (i < 0 || i > curlen) {  // i小于0或者大于表长
                throw new Exception("插入位置不合理");
            }
            for (int j = curlen; j > i; j--) {
                r[j] = r[j - 1];   // 插入位置及之后的元素后移
            }
            r[i] = x;   // 插入x
            this.curlen++;  // 表长度增1
        }

[0fcb03f19a1d429a925ec592023a1198.png]: https://img-blog.csdnimg.cn/0fcb03f19a1d429a925ec592023a1198.png
[76563fc45cca48f790999dab731b97e0.png]: https://img-blog.csdnimg.cn/76563fc45cca48f790999dab731b97e0.png