排序概念以及插入排序

一、排序基本概念

1.就地排序：使用恒定的额外空间来产生输出

就地排序只是在原数组空间进行排序处理，也就是输入的数组和得到的数组是同一个

2.内部排序和外部排序：待排序数据可以一次性载入到内存中为内部排序，反之数据量过大就是外部排序

本科阶段几乎都是内部排序

3.稳定排序：排序前后序列中键值相等的元素在相对位置不发生变化的就是稳定排序

4.哪些排序是稳定和不稳定：

a.冒泡排序（Bubble sort），插入排序（Insrtion sort），归并排序（Merge sort）和计数排序（Counting sort）等本身就具有稳定排序的特质

b.快速排序、堆排序等是不稳定排序

c.虽然很多算法本身具有稳定或不稳定排序性质但是任何排序只要稍作修改就可以修改稳定性，例如在冒泡排序中判断交换顺序的依据是if(a>b)只要变成if(a>=b)就可以破坏稳定性

二、插入排序

特点：

1,经过几次排序后,前几个元素就已经有序了,后序元素是否有序无关

2,怕新元素是前面已经有序元素的最小值

3.如果待排序的元素，已经有序，只有极个别的元素是无序,插入速度较快

4.如果元素是链式存储，非常时候插入排序

三、代码实现

1.头文件中的接口

//
// Created by 27893 on 2025/8/9.
//

#ifndef INSERTSORT_H
#define INSERTSORT_H
typedef struct {
	int key;
	void*data;
}Element;

typedef struct {
	Element*data;
	int len;
}SortTable;

void insertSort(SortTable*table);
#endif //INSERTSORT_H

2.算法的实现

//
// Created by 27893 on 2025/8/9.
//

#include "InsertSort.h"

void insertSort(SortTable *table) {
	//从第二个开始插入
	for (int i=1;i<table->len;i++) {
		if (table->data[i].key<table->data[i-1].key) {
			//用j来辅助查找元素的真正待插入位置
			int temp=table->data[i].key;
			int j=i-1;
			//只要待插入元素比j指向位置还小就往前
			while (j!=-1&&temp<table->data[j].key) {
				table->data[j+1].key=table->data[j].key;
				j--;
			}
			//否则结束插入到j的后一个位置
			table->data[j+1].key=temp;
		}
	}
}

四、希尔排序

1.希尔排序说明

在插入排序中，我们可能会遇到一个很小的数到很后面才发现，这样就要和前面有序区的很多元素进行比较,时间复杂度接近O(n^2)

而希尔排序是将每次步长调大一点，刚开始一般为数组长度的一半，比如下面的表元素个数为10，我们第一次排序就拿当前元素与当前元素后面的第5个进行比较，这样的比较进行5次

第二次我们步长为上次的一半，每次和自己后面的第2个进行比较，这样的比较进行两次

直到步长为0，结束我们的循环，这样时间复杂度最多为O(nlog_2n)

2.希尔排序代码

void shellSort(SortTable *table) {
	for (int gap=table->len/2;gap>0;gap/=2) {
		for (int i=gap;i<table->len;i++) {
			Element temp=table->data[i];
			int j;
			for (j=i;j>=gap&&temp.key<table->data[j-gap].key;j-=gap) {
				table->data[j]=table->data[j-gap];
			}
			table->data[j]=temp;
		}
	}
}