排序

排序的概念及其运用

排序的概念

==排序：==所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
==稳定性：==假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
==内部排序：==数据元素全部放在内存中的排序。
==外部排序：==数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

排序运用

来上京东

大学排名

常见的排序算法

常见排序算法的实现

插入排序

基本思想

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

实际中我们玩扑克牌时，就用了插入排序的思想

但是数组肯定不是有序的，所以我们得先让数组有序

先把打印数组给剥离出来

// 打印数组
void PrintArray(int* a, int n) {
	assert(a);
	int i = 0;
	for (i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
}

插入排序

// 插入排序
void InsertSort(int* a, int n) {
	assert(a);
	int i = 0;
	for (i = 0; i < n - 1; i++)	{
		int end = i;
		int x = a[end+1];
		while (end >= 0) {
			//要插入的数比顺序中的数小就准备挪位置
			if (a[end] > x) {
				a[end + 1] = a[end];
				end--;
			}
			else {
				//插入的数比顺序中的要大就跳出
				break;
			}
		}
		//跳出来两种情况
		//1.end == -1 的时候
		//2.break 的时候
		//把x给end前面一位
		a[end + 1] = x;
	}
}

插入排序的时间复杂度：O(N²)

最好：O(N) — 顺序有序 （接近有序）

最坏：O(N²) — 逆序

插入排序的空间复杂度：O(1)

希尔排序( 缩小增量排序 ) (反正希尔牛逼)

希尔排序是在优化直接插入排序，而且效果超级明显，为什么是优化呢，因为我们知道直接插入排序接近有序了就会非常快，那我就创造这样的有序，让他时间复杂度接近O(N)，我们知道排序的时间复杂度最好情况就是O(N)，而我们接近O(N)也是相当了不起了，基本是接近天花板了

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

希尔排序步骤

1.分组预排序 ---- 数组接近有序

按gap分组，对分组值进行插入排序 分成gap组

2.直接插入排序 数组接近有序，直接插入的时间复杂度就是O(N)

单组多躺

多组插入

间距为gap多组预排实现的时间复杂度O(gap*(1+…+N/gap))

最好：O(N)

最好：O(N)

最坏：O(gap*(1+…+N/gap))

gap越大，预排越快，预排后越不接近有序

gap越小，预排越慢，预排后越接近有序

多组一锅炖（要是分组插麻烦我们也可以一锅炖）

多次预排序(gap > 1)+直接插入（gap == 1）

gap/2

gap/3

时间复杂度O(N^1.3)记住就行，反正记住希尔很牛逼就行，希尔排序很快

测直接插入排序和希尔排序的性能（让你看看什么才叫希尔排序）

代码

Sort.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>

// 排序实现的接口
// 打印数组
extern void PrintArray(int* a, int n);
// 插入排序
extern void InsertSort(int* a, int n);
// 希尔排序
extern void ShellSort(int* a, int n);
// 选择排序
extern void SelectSort(int* a, int n);
// 堆排序
extern void AdjustDwon(int* a, int n, int root);
extern void HeapSort(int* a, int n);
// 冒泡排序
extern void BubbleSort(int* a, int n);
// 快速排序递归实现
// 快速排序hoare版本
extern int PartSort1(int* a, int left, int right);
// 快速排序挖坑法
extern int PartSort2(int* a, int left, int right);
// 快速排序前后指针法
extern int PartSort3(int* a, int left, int right);
extern void QuickSort(int* a, int left, int right);
// 快速排序 非递归实现
extern void QuickSortNonR(int* a, int left, int right);
// 归并排序递归实现
extern void MergeSort(int* a, int n);
// 归并排序非递归实现
extern void MergeSortNonR(int* a, int n);
// 计数排序
extern void CountSort(int* a, int n);

Sort.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "Sort.h"

// 打印数组
void PrintArray(int* a, int n) {
	assert(a);
	int i = 0;
	for (i = 0; i < n; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
}
// 插入排序
void InsertSort(int* a, int n) {
	assert(a);
	int i = 0;
	for (i = 0; i < n - 1; i++)	{
		int end = i;
		int x = a[end+1];
		while (end >= 0) {
			//要插入的数比顺序中的数小就准备挪位置
			if (a[end] > x) {
				a[end + 1] = a[end];
				end--;
			}
			else {
				//插入的数比顺序中的要大就跳出
				break;
			}
		}
		//跳出来两种情况
		//1.end == -1 的时候
		//2.break 的时候
		//把x给end前面一位
		a[end + 1] = x;
	}
}
// 希尔排序
void ShellSort(int* a, int n) {
	//分组
	int gap = n;
	//多次预排序（gap>1）+ 直接插入（gap == 1）
	while (gap>1){
		//gap /= 2;
		//除以三我们知道不一定会过1，所以我们+1让他有一个必过1的条件
		gap = gap / 3 + 1;
		//单组多躺
		int i = 0;
		for (i = 0; i < n - gap; i++) {
		int end = i;
		int x = a[end + gap];
		while (end >= 0) {
			if (a[end] > x) {
				a[end + gap] = a[end];
				//步长是gap
				end -= gap;
			}
			else {
				break;
			}
		}
		a[end + gap] = x;
	}
	}	
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1

#include "Sort.h"

// 测试排序的性能对比
void TestOP()
{
	//设置随机起点
	srand(time(NULL));
	//将要创建的数组大小
	const int N = 100000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; ++i)
	{
		//保证两个数组是一样的
		a1[i] = rand();
		a2[i] = a1[i];
	}
	int begin1 = clock();//开始时间
	InsertSort(a1, N);
	int end1 = clock();  //结束时间
	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();
	int begin3 = clock();
	printf("InsertSort:%d\n", end1 - begin1);//结束时间减去开始时间 
	printf("ShellSort:%d\n", end2 - begin2);
	free(a1);
	free(a2);
}
//测试插入排序
void TestInsertSort() {
	int a[] = { 1,5,3,7,0,9 };
	InsertSort(a, sizeof(a) / sizeof(a[0]));	
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}
//测试希尔排序
void TestShellSort() {
	int a[] = { 9,1,2,5,7,4,8,6,3,5 };
	ShellSort(a, sizeof(a) / sizeof(a[0]));
	PrintArray(a, sizeof(a) / sizeof(a[0]));
}
int main(){
	//TestInsertSort();
	//TestShellSort();
	TestOP();
	return 0;
}