目錄
一、排序的概念
二、插入排序??
1、直接插入排序?
特性總結(jié)：
2、希爾排序
特性總結(jié)：
?三、選擇排序
1、直接選擇排序?
特性總結(jié)：
2、堆排序—排升序(建大堆)
向下調(diào)整函數(shù)
堆排序函數(shù)
特性總結(jié)：
代碼完整版：?
?頭文件
?函數(shù)文件
?測試文件
一、排序的概念
?
二、插入排序??
1、直接插入排序?
直接插入排序是一種簡單的排序算法，它的基本思想是將一個記錄插入到已經(jīng)排序好的有序表中，從而得到一個新的、記錄數(shù)增加1的有序表。這個算法適用于少量數(shù)據(jù)的排序，是穩(wěn)定的排序方法，即相等的元素的順序不會改變。
直接插入排序的算法過程如下：
- 從第一個元素開始，該元素可以認為已經(jīng)被排序；
- 取出下一個元素，在已經(jīng)排序的元素序列中從后向前掃描；
- 如果該元素（已排序）大于新元素，將該元素移到下一位置；
- 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置；
- 將新元素插入到該位置后；
- 重復步驟2~5。
如果我們將這個過程比作撲克牌的排序，每次我們都是從牌堆中拿出一張牌，然后將它插入到左手中正確的位置，最終左手中的牌都是排序好的。
?我們來看一下代碼的運行過程：
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++) {
int end = i;
int tmp = a[i + 1];
while (end >= 0) {
if (a[end] > tmp) {
a[end + 1] = a[end];
end--;
}
else {
break;
}
}
a[end + 1] = tmp;
}
}- 函數(shù)參數(shù)：指針a接收數(shù)組，n接收數(shù)組元素個數(shù)。
- 首先，外層循環(huán)從第一個元素開始遍歷到倒數(shù)第二個元素，因為在內(nèi)層循環(huán)中需要比較當前元素和前一個元素的大小，所以最后一個元素不需要再比較。
- 在外層循環(huán)中，我們將當前元素的下一個元素作為待插入元素，將當前元素的下標保存在變量end中，這個變量表示當前元素在已排序部分中的位置。
- 接下來while循環(huán)中，我們在已排序部分從后往前遍歷，比較當前元素和已排序部分中的元素大小，如果當前元素小于已排序部分中的元素，則將已排序部分中的元素后移一位，直到找到當前元素的正確位置。
- 最后，我們將待插入元素插入到正確的位置，即end+1的位置。
- 內(nèi)層循環(huán)結(jié)束后，當前元素已經(jīng)被插入到了正確的位置，我們繼續(xù)外層循環(huán)，處理下一個元素，直到所有元素都被插入到正確的位置。
特性總結(jié)：
1. 元素集合越接近有序，直接插入排序算法的時間效率越高2. 時間復雜度：O(N^2)3. 空間復雜度：O(1)，它是一種穩(wěn)定的排序算法4. 穩(wěn)定性：穩(wěn)定
2、希爾排序
?希爾排序（Shell Sort）是一種改進的插入排序算法，它的基本思想是將待排序的序列分成若干個子序列，對每個子序列進行插入排序，然后再將整個序列進行一次插入排序。通過這種方式，可以使得序列中較小的元素盡可能地快速地移動到前面，從而減少了插入排序的比較次數(shù)和移動次數(shù)，提高了排序的效率。
希爾排序的算法過程如下：
- 選擇一個增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 按增量序列個數(shù)k，對序列進行k趟排序；
- 每趟排序，根據(jù)對應(yīng)的增量ti，將待排序列分割成若干長度為m的子序列，分別對每個子序列進行插入排序；
- 將各個子序列中的排序結(jié)果合并成一個序列。
代碼如下：
void ShellSort(int* a, int n)
{
//1、gap > 1 預排序
//2、gap == 1 直接插入排序
int gap = n;
while (gap > 1) {
gap = gap / 3 + 1;// +1可以保證最后一次一定是1
for (int i = 0; i < n - gap; i++) {
int end = i;
int tmp = a[end + gap];
while (end >= 0) {
if (a[end] > tmp) {
a[end + gap] = a[end];
end -= gap;
}
else {
break;
}
}
a[end + gap] = tmp;
}
}
}- 首先，我們選擇一個增量gap=n，然后將序列分成若干個子序列，對每個子序列進行插入排序。
- 在這個實現(xiàn)中，我們使用了一個while循環(huán)來計算增量gap，每次將gap除以3并加1，保證gap最小為1，此時進行直接插入排序。
- 在外層while循環(huán)中，我們將序列分成若干個子序列，每個子序列的長度為gap。然后，我們對每個子序列進行插入排序，將子序列中的元素插入到已排序部分的正確位置。
-
在內(nèi)層循環(huán)中，我們使用了一個變量end來表示當前元素的下標，每次將end減去gap，直到找到當前元素的正確位置。然后，我們將待插入元素插入到正確的位置，即end+gap的位置。
-
內(nèi)層循環(huán)結(jié)束后，當前子序列已經(jīng)排好序了，我們繼續(xù)外層while循環(huán)，處理下一個子序列，直到所有子序列都被排好序了。
?以數(shù)組 a = [9, 8, 7, 6, 5, 4, 3, 3, 2, 1, 0]，長度 n = 11為例，演示排序過程
圖中顏色相同的值為當前<間距gap>下的子序列，從前往后依次比較每個子序列（也就是相距 gap 個位置的值的大小）。
特性總結(jié)：
- 希爾排序是對直接插入排序的優(yōu)化。
- 當gap > 1時都是預排序，目的是讓數(shù)組更接近于有序。當gap == 1時，數(shù)組已經(jīng)接近有序的了，這樣就會很快。這樣整體而言，可以達到優(yōu)化的效果。我們實現(xiàn)后可以進行性能測試的對比。
- 希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算，因此在好些書中給出的希爾排序的時間復雜度都不固定，但我們只需記住結(jié)論：O（N^ 1.3），復雜的推導和計算過程不需要了解。
?三、選擇排序
1、直接選擇排序?
第一種：通過不斷選擇未排序序列中的最小元素，并將其放到已排序序列的末尾，逐步構(gòu)建有序序列。外層循環(huán)控制已排序序列的末尾位置，內(nèi)層循環(huán)用于找到未排序序列中的最小元素。通過不斷交換位置，將最小元素放到已排序序列的末尾，直到整個數(shù)組排序完成。
void SelectSort(int arr[], int n) {
int i, j, minIndex, temp;
for (i = 0; i < n-1; i++) {
minIndex = i;
for (j = i+1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}第二種：通過每一輪的比較，找到最大值和最小值，將最大值的節(jié)點跟右邊交換，最小值節(jié)點跟左邊交換，達到排升序的效果。
我們先看代碼，然后通過一個例子就能明白了。?
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int maxi = begin, mini = begin;
for (int i = begin; i <= end; i++)
{
if (a[i] > a[maxi])
{
maxi = i;
}
if (a[i] < a[mini])
{
mini = i;
}
}
Swap(&a[begin], &a[mini]);
// 如果maxi和begin重疊，修正一下即可
if (begin == maxi)
{
maxi = mini;
}
Swap(&a[end], &a[maxi]);
++begin;
--end;
}
}- 代碼中的變量begin和end分別表示當前未排序的元素范圍的起始和結(jié)束位置。
- 在while循環(huán)中，每次從begin到end的范圍內(nèi)找到最大和最小的元素，分別用maxi和mini記錄它們的下標。
- 然后將mini所指向的元素與begin所指向的元素交換位置，將maxi所指向的元素與end所指向的元素交換位置。
- 如果maxi和begin重疊，說明mini所指向的元素是當前未排序元素中最大的，需要將maxi更新為mini。
- 最后，begin指針向后移動一位，end指針向前移動一位，繼續(xù)進行下一輪排序。?
我們來用一個簡單的例子演示一下這個選擇排序算法的過程。
假設(shè)我們有一個數(shù)組`a`，它的元素為：[5, 3, 8, 6, 4, 2]，我們要對它進行排序。
首先，begin指向第一個元素，end指向最后一個元素：
begin = 0
end = 5接下來，我們進入主循環(huán)，因為`begin`小于`end`，所以我們需要繼續(xù)排序。在第一輪排序中，我們需要找到未排序部分的最大值和最小值。
首先，我們將`maxi`和`mini`都初始化為`begin`，也就是第一個元素的索引。然后，我們遍歷未排序部分的元素，找到最大值和最小值的索引。在這個例子中，最大值的索引是2，最小值的索引是5。
maxi = 2
mini = 5接下來，我們將未排序部分的最小值交換到開始位置，將未排序部分的最大值交換到結(jié)束位置。這時，數(shù)組的狀態(tài)變?yōu)椋篬2,?3,?5,?6, 4, 8]
由于我們已經(jīng)將當前范圍的最大值和最小值放到了正確的位置，所以我們將`begin`向后移動一位，將`end`向前移動一位，繼續(xù)進行下一輪排序。此時，`begin`指向第二個元素，`end`指向倒數(shù)第二個元素：
begin = 1
end = 4在第二輪排序中，我們需要找到未排序部分的最大值和最小值。這時，最大值的索引是3，最小值的索引是1。
maxi = 3
mini = 1接下來，將未排序部分的最小值交換到開始位置，將未排序部分的最大值交換到結(jié)束位置。這時，數(shù)組的狀態(tài)變?yōu)椋篬2, 3, 5, 4, 6, 8]?
進行下一輪排序。此時，`begin`指向第三個元素，`end`指向第四個元素：?
begin = 2
end = 3?在第三輪排序中，我們需要找到未排序部分的最大值和最小值。這時，最大值的索引是2，最小值的索引是1。?文章來源：http://www.zghlxwxcb.cn/news/detail-809155.html
maxi = 2
mini = 3最后，我們將未排序部分的最小值交換到開始位置，將未排序部分的最大值交換到結(jié)束位置。這時，數(shù)組的狀態(tài)變?yōu)椋篬2, 3, 4, 5, 6, 8]，所有元素都排序完成，排序結(jié)束。文章來源地址http://www.zghlxwxcb.cn/news/detail-809155.html
特性總結(jié)：
- 直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用
- 時間復雜度：每一輪比較都需要遍歷數(shù)組，查找最大最小值，第一輪遍歷N個數(shù)據(jù)，第二輪是N-2個數(shù)據(jù)，第三輪N-4 …，遍歷次數(shù)為：N+N-2+N-4+…+1，一個等差數(shù)列求和，所以總的時間復雜度為O(N^2)
- 空間復雜度：O(1)
- 穩(wěn)定性：不穩(wěn)定
2、堆排序—排升序(建大堆)
向下調(diào)整函數(shù)
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n){
if (child + 1 < n && a[child + 1] > a[child])
++child;
if (a[child] > a[parent]){
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}- 通過傳入?yún)?shù)獲取到當前的左子節(jié)點的位置。
- 當child位置小于數(shù)組元素個數(shù)時進行判斷。
- 進入循環(huán)，首先判斷檢查右子節(jié)點是否存在并且比左子節(jié)點的值大，如果是，將?
child?更新為右子節(jié)點的索引，以確保選擇更小的子節(jié)點進行比較。 - 比較選定的子節(jié)點的值與父節(jié)點的值，如果子節(jié)點的值大于父節(jié)點的值，就交換它們。
- 更新parent為新的子節(jié)點位置，更新child為新的左子節(jié)點位置，然后繼續(xù)比較和交換，直到不再需要交換為止。
- 如果當前子節(jié)點不大于當前父節(jié)點則停止循環(huán)。
堆排序函數(shù)
// 排升序
void HeapSort(int* a, int n)
{
// 建大堆
for (int i = (n-1-1)/2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}- ?在HeapSort函數(shù)中，第一個循環(huán)調(diào)用了AdjustDown函數(shù)，將待排序數(shù)組構(gòu)建成了一個大堆。但是，這個大堆并不是完全有序的，只是滿足了大堆的性質(zhì)，即每個節(jié)點的值都大于或等于其左右子節(jié)點的值。因此，需要進行第二個while循環(huán)，將大堆中的元素依次取出，交換堆頂元素和數(shù)組末尾元素，并重新調(diào)整大堆，直到整個數(shù)組有序。
- 第二個while循環(huán)中，將堆頂元素與數(shù)組末尾元素交換，然后將剩余元素重新調(diào)整為大堆。這樣，每次交換后，數(shù)組末尾的元素就是當前大堆中的大值，而剩余元素仍然滿足大堆的性質(zhì)。重復以上步驟，直到整個數(shù)組有序。
特性總結(jié)：
- 堆排序使用堆來選數(shù)，效率就高了很多。
- 時間復雜度：O(N*logN)
- 空間復雜度：O(1)
- 穩(wěn)定性：不穩(wěn)定
代碼完整版：?
?頭文件
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
void PrintArray(int* a, int n);
void InsertSort(int* a, int n);
void ShellSort(int* a, int n);
void SelectSort(int* a, int n);
void HeapSort(int* a, int n);?函數(shù)文件
#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[i + 1];
while (end >= 0) {
if (a[end] > tmp) {
a[end + 1] = a[end];
end--;
}
else {
break;
}
}
a[end + 1] = tmp;
}
}
void ShellSort(int* a, int n)
{
//1、gap > 1 預排序
//2、gap == 1 直接插入排序
int gap = n;
while (gap > 1) {
gap = gap / 3 + 1;// +1可以保證最后一次一定是1
for (int i = 0; i < n - gap; i++) {
int end = i;
int tmp = a[end + gap];
while (end >= 0) {
if (a[end] > tmp) {
a[end + gap] = a[end];
end -= gap;
}
else {
break;
}
}
a[end + gap] = tmp;
}
}
}
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int maxi = begin, mini = begin;
for (int i = begin; i <= end; i++)
{
if (a[i] > a[maxi])
{
maxi = i;
}
if (a[i] < a[mini])
{
mini = i;
}
}
Swap(&a[begin], &a[mini]);
// 如果maxi和begin重疊，修正一下即可
if (begin == maxi)
{
maxi = mini;
}
Swap(&a[end], &a[maxi]);
++begin;
--end;
}
}
void AdjustDown(int* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n) {
if (child + 1 < n && a[child + 1] > a[child]) {
child++;
}
if (a[child] > a[parent]) {
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else {
break;
}
}
}
void HeapSort(int* a, int n)
{
for (int i = (n - 1 - 1) / 2; i >= 0; --i) {
AdjustDown(a, n, i);
}
int end = n - 1;
while (end > 0) {
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
end--;
}
}
?測試文件
#include"Sort.h"
#include<time.h>
void TestInsertSort()
{
//int a[] = { 4,7,1,9,3,4,5,8,3,2 };
int a[] = { 4,7,1,9,3,6,5,8,3,2,0 };
PrintArray(a, sizeof(a) / sizeof(int));
InsertSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
void TestSelectSort()
{
//int a[] = { 4,7,1,9,3,6,5,8,3,2,0 };
int a[] = { 9,7,1,3,3,0,5,8,3,2,3 };
PrintArray(a, sizeof(a) / sizeof(int));
SelectSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
void TestHeapSort()
{
int a[] = { 4,7,1,9,3,6,5,8,3,2,0 };
PrintArray(a, sizeof(a) / sizeof(int));
HeapSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
void TestOP()
{
srand(time(0));
const int N = 1000000;//運行時間較長可自行更改大小
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
int* a3 = (int*)malloc(sizeof(int) * N);
int* a4 = (int*)malloc(sizeof(int) * N);
int* a5 = (int*)malloc(sizeof(int) * N);
int* a6 = (int*)malloc(sizeof(int) * N);
int* a7 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
a1[i] = rand();
a2[i] = a1[i];
a3[i] = a1[i];
a4[i] = a1[i];
a5[i] = a1[i];
a6[i] = a1[i];
a7[i] = a1[i];
}
int begin1 = clock();
InsertSort(a1, N);
int end1 = clock();
int begin2 = clock();
ShellSort(a2, N);
int end2 = clock();
int begin3 = clock();
SelectSort(a3, N);
int end3 = clock();
int begin4 = clock();
HeapSort(a4, N);
int end4 = clock();
printf("InsertSort:%d\n", end1 - begin1);
printf("ShellSort:%d\n", end2 - begin2);
printf("SelcetSort:%d\n", end3 - begin3);
printf("HeapSort:%d\n", end4 - begin4);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
}
int main()
{
//TestInsertSort();
//TestShellSort();
//TestSelectSort();
//TestHeapSort();
TestOP();
return 0;
}
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法—插入排序&選擇排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
