一.排序
1.1.排序的概念及其運(yùn)用
1.1.1排序的概念
排序： 所謂排序，就是使一串記錄，按照其中的某個(gè)或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。
穩(wěn)定性： 假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對(duì)次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn)定的；否則稱為不穩(wěn)定的。
內(nèi)部排序： 數(shù)據(jù)元素全部放在內(nèi)存中的排序。
外部排序： 數(shù)據(jù)元素太多不能同時(shí)放在內(nèi)存中，根據(jù)排序過程的要求不能在內(nèi)外存之間移動(dòng)數(shù)據(jù)的排序。
1.1.2排序運(yùn)用
1.1.3 常見的排序算法
二.插入排序
2.1.直接插入排序
2.1.1.算法講解
直接插入排序是一種簡(jiǎn)單的插入排序法，其基本思想是：
把待排序的記錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個(gè)新的有序序列 。
實(shí)際中我們玩撲克牌時(shí)，就用了插入排序的思想
當(dāng)插入第i(i>=1)個(gè)元素時(shí)，前面的array[0],array[1],…,array[i-1]已經(jīng)排好序，此時(shí)用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進(jìn)行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移
直接插入排序的特性總結(jié)：
- 元素集合越接近有序，直接插入排序算法的時(shí)間效率越高
- 時(shí)間復(fù)雜度：O(N^2)
- 空間復(fù)雜度：O(1)，它是一種穩(wěn)定的排序算法
- 穩(wěn)定性：穩(wěn)定
2.1.2.代碼實(shí)現(xiàn)
2.1.2.1.函數(shù)定義
Sort.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<time.h>
//打印
void PrintArray(int* a, int n);
//插入排序
void InsertSort(int* a, int n);
2.1.2.2.算法接口實(shí)現(xiàn)
Sort.c
#include"Sort.h"
//打印
void PrintArray(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
//直接插入排序
void InsertSort(int* a, int n)
{
for (int i = 0; i < n-1; i++)
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
end--;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
2.1.2.3.測(cè)試代碼實(shí)現(xiàn)
test.c
#include"Sort.h"
void TestInsertSort()
{
int a[] = { 2,4,5,7,8,0,9,6,3,1 };
printf("排序前：");
PrintArray(a, sizeof(a) / sizeof(int));
printf("\n");
printf("直接插入排序：");
InsertSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{
TestInsertSort();
return 0;
}
2.1.2.4.測(cè)試展示
2.2.希爾排序
2.2.1.算法講解
希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個(gè)整數(shù)，把待排序文件中所有記錄分成個(gè)組，所有距離為的記錄分在同一組內(nèi)，并對(duì)每一組內(nèi)的記錄進(jìn)行排序。然后，取，重復(fù)上述分組和排序的工作。當(dāng)?shù)竭_(dá)=1時(shí)，所有記錄在統(tǒng)一組內(nèi)排好序。
希爾排序的特性總結(jié)：文章來源：http://www.zghlxwxcb.cn/news/detail-754964.html
- 希爾排序是對(duì)直接插入排序的優(yōu)化。
- 當(dāng)gap > 1時(shí)都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時(shí)，數(shù)組已經(jīng)接近有序的了，這樣就會(huì)很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。我們實(shí)現(xiàn)后可以進(jìn)行性能測(cè)試的對(duì)比。
- 希爾排序的時(shí)間復(fù)雜度不好計(jì)算，因?yàn)間ap的取值方法很多，導(dǎo)致很難去計(jì)算，因此在好些樹中給出的希爾排序的時(shí)間復(fù)雜度都不固定:
《數(shù)據(jù)結(jié)構(gòu)(C語言版)》— 嚴(yán)蔚敏
《數(shù)據(jù)結(jié)構(gòu)-用面相對(duì)象方法與C++描述》— 殷人昆
- 穩(wěn)定性：不穩(wěn)定
2.2.2.代碼實(shí)現(xiàn)
2.2.2.1.函數(shù)定義
Sort.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<time.h>
//打印
void PrintArray(int* a, int n);
//希爾排序
void ShellSort(int* a, int n);
2.2.2.2.算法接口實(shí)現(xiàn)
Sort.c
#include"Sort.h"
//打印
void PrintArray(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
//希爾排序
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
2.2.2.3.測(cè)試代碼實(shí)現(xiàn)
test.c
#include"Sort.h"
void TestShellSort()
{
int a[] = { 2,4,5,7,8,0,9,6,3,1 };
printf("排序前：");
PrintArray(a, sizeof(a) / sizeof(int));
printf("\n");
printf("希爾排序：");
ShellSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{
TestShellSort();
return 0;
}
2.2.2.4.測(cè)試展示
文章來源地址http://www.zghlxwxcb.cn/news/detail-754964.html
到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu) — 排序 — 插入排序】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
