← 数据结构基础

内排序

数据结构-内排序

所谓排序,是要整理表中的记录,使之按关键字递增(或递减)的有序排列。
内排序全称为内部排序。内部排序是指待排序列完全存放在内存中所进行的排序过程,适合不太大的元素序列。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。
待排序的顺序表中数据元素的类型定义如下(类似于被查找的顺序表元素类型):
typedef int KeyType;    // 关键字的数据类型typedef struct{    KeyType key;    InfoType data;        // 其他数据, 可选} RecType;

插入排序

插入排序的基本思想是:每次将一个待排序的记录,按其关键字大小插入到前面已经排好序的子表中的适当位置,直到全部记录插入完成为止。
两种插入排序方法:
  • 直接插入排序(含二分插入排序)
  • 希尔排序

直接插入排序

直接插入排序方法中:每趟插入只排好一个数n个数要进行n − 1趟插入排序才能全部排好。
//对R[0..n-1]按递增有序进行直接插入排序void insertSort(RecType R[], int n){    int i, j;    RecType tmp;    for (i = 1; i < n; i++)    {        tmp = R[i];        j = i - 1;        // 从右向左在有序区R[0..i-1]找R[i]的插入位置        while (j >= 0 && tmp.key < R[j].key)        {            R[j + 1] = R[j];    // 将关键字大于R[i].key的记录后移            j--;        }        R[j + 1] = tmp;         // 在j+1处插入R[i]    }}
1391679-20180618165919523-196396537

交换排序

交换排序的基本思想:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。
两种交换排序方法:
  • 冒泡排序
  • 快速排序

冒泡排序

冒泡排序方法中:n个数要进行n − 1趟冒泡排序才能全部排好;每趟冒泡要比较n − j次(1 <  = j <  = n − 1),每趟只排好一个数
// 冒泡排序void bubbleSort(RecType R[], int n){    int i, j;    RecType temp;    for (i = 0; i < n - 1; i++)    {        // 比较找本趟最小关键字的记录        for (j = i; j < n - 1; j++)        {            // 递增排序(如果前者大于后者, 则交换)            if (R[j].key > R[j + 1].key)            {                temp = R[j];    //R[j]与R[j-1]进行交换                R[j] = R[j + 1];                R[j + 1] = temp;            }        }    }}
1391679-20180618163321525-1936669878

选择排序

选择排序的基本思想是:每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子表的最后,直到全部记录排序完毕。
两种选择排序方法:
  • 简单选择排序(或称直接选择排序)
  • 堆排序

简单选择排序

简单选择排序方法中:每趟选择只排好一个数n个数要进行n − 1趟选择排序才能全部排好。
// 简单选择排序void selectSort(RecType R[], int n){    int i, j, k;    RecType temp;    for (i = 0; i < n - 1; i++)   // 做第i趟排序    {        k = i;        // 在[i..n-1]中选key最小的R[k]        for (j = i + 1; j < n; j++)        {            // k记下的最小关键字所在的位置            if (R[j].key < R[k].key) k = j;        }        // 交换R[i]和R[k]        if (k != i)        {            temp = R[i];            R[i] = R[k];            R[k] = temp;        }    }}
QQ20210110-202936-HD

Nobelium is built with ♥ and ⚛ Next.js. Proudly deployed on ▲Vercel.

© Ashinch 2021 桂ICP备18011166号-1