1.直接插入排序算法

?1?//?直接插入排序
?2?//Code?by?Larman?Yuan?2009-6-28
?3?
?4?#include?"stdafx.h"
?5?
?6?void?insertSort(int?*?sortArray,?int?size)
?7?{
?8?????int?j;
?9?????for(int?i?=?1;?i?<?size;?i++)
10?????{
11?????????j?=?i?-?1;
12?????????int?temp?=?sortArray[i];
13?????????while(sortArray[j]??>?temp?&&?j?>=?0)
14?????????{
15?????????????sortArray[j?+?1]?=?sortArray[j];
16?????????????j--;
17?????????}
18?????????if(j?!=?(i?-?1))
19?????????????sortArray[j?+?1]?=?temp;
20?
21?????}
22?}
23?
24?void?printArray(int?arrayToPrint[],int?size)
25?{
26????????for(int?i?=?0;?i?<?size;?i++)
27?????{
28?????????printf("%d?",?arrayToPrint[i]);
29?????}
30?????printf("\n");
31?}
32?int?_tmain(int?argc,?_TCHAR*?argv[])
33?{
34?????int??sortArray[8]?=?{49,?38,?65,?97,76,?13,?27,?49};
35?????printf("Array?before?sort:?");
36?????printArray(sortArray,?8);
37?????insertSort(sortArray,?8);
38?????????printf("Array?after?sort?:?");
39?????printArray(sortArray,?8);
40?????return?0;
41?}

?運(yùn)行結(jié)果：

Array before sort: 49 38 65 97 76 13 27 49?

Array after sort : 13 27 38 49 49 65 76 97?

?

2.二分插入排序算法

?1?//?二分法插入排序
?2?//Code?by?Larman?Yuan?2009-6-28
?3?
?4?#include?"stdafx.h"
?5?
?6?void?binInsertSort(int*?sortArray,?int?size)
?7?{
?8?????int?left,?right,middle,?i,j,?temp;
?9?????for(i?=?1;?i?<?size;?i++)
10?????{
11?????????temp?=?sortArray[i];
12?????????left?=?0;
13?????????right?=?i?-?1;
14?
15?????????while(left?<=?right)
16?????????{
17?????????????middle?=?(left?+?right)?/?2;
18?????????????if(temp?<?sortArray[middle])
19?????????????????right?=?middle?-1;
20?????????????else
21?????????????????left?=?middle?+?1;
22?????????}
23?
24?????????for(j?=?i?-?1;?j?>=?left;?j--)
25?????????????sortArray[j?+?1]?=?sortArray[j];
26?????????if(left?!=?i)
27?????????????sortArray[left]?=?temp;
28?????}
29?}
30?
31?void?printArray(int?arrayToPrint[],int?size)
32?{
33????????for(int?i?=?0;?i?<?size;?i++)
34?????{
35?????????printf("%d?",?arrayToPrint[i]);
36?????}
37?????printf("\n");
38?}
39?
40?int?_tmain(int?argc,?_TCHAR*?argv[])
41?{
42?????int??sortArray[8]?=?{49,?38,?65,?97,76,?13,?27,?49};
43?????printf("Array?before?sort:?");
44?????printArray(sortArray,?8);
45?????binInsertSort(sortArray,?8);
46?????????printf("Array?after?sort?:?");
47?????printArray(sortArray,?8);
48?????return?0;
49?}

運(yùn)行結(jié)果：

Array before sort: 49 38 65 97 76 13 27 49?

Array after sort : 13 27 38 49 49 65 76 97?

?

3.表插入排序算法

?1?//?表插入排序
?2?//Code?by?larman?Yuan?2009-6-28
?3?
?4?#include?"stdafx.h"
?5?#include?<stdlib.h>
?6?struct?Node;
?7?typedef?struct?Node?ListNode;
?8?struct?Node
?9?{
10?????int?key;
11?????ListNode*?next;
12?};
13?typedef?ListNode*?LinkList;
14?
15?void?listInsertSort(LinkList?*?palist)
16?{
17?????ListNode?*?now,?*pre,?*p,?*q,?*head;
18?????head?=?*palist;
19?????pre?=?head?->next;
20?????now?=?pre->next;
21?????if(pre?==?NULL?||?now?==?NULL)
22?????{
23?????????return;
24?????}
25?????while(now?!=?NULL)
26?????{
27?????????q?=?head;
28?????????p?=?head->next;
29?????????while(p?!=?now?&&?p->key?<=?now->key)
30?????????{
31?????????????q?=?p;
32?????????????p?=?p->next;
33?????????}
34?????????if(p?==?now)
35?????????{
36?????????????pre?=?pre->next;
37?????????????now?=?pre->next;
38?????????????continue;
39?????????}
40?????????pre->next?=?now->next;
41?????????q->next?=?now;
42?????????now->next?=?p;
43?????????now?=?pre->next;
44?????}
45?}
46?
47?void?printList(LinkList?*?palist)
48?{
49?????ListNode?*?p?=?(*palist)->next;
50?????????while(p?!=?NULL)
51?????????{
52?????????????printf("%d?",p->key);
53?????????????p?=?p->next;
54?????????}
55?????????printf("\n");
56?}
57?
58?void?insertElement(LinkList?*?palist,?int?value)
59?{
60?????ListNode?*?head,?*p,?*?nodeToInsert;
61?????if(palist?==?NULL?||?*palist?==?NULL)
62?????{
63?????????return;
64?????}
65?????head?=?*palist;
66?????p?=?head;
67?????while(p->next?!=?NULL)
68?????{
69?????????p?=?p->next;
70?????}
71?????nodeToInsert?=?(ListNode?*)malloc(sizeof(struct?Node));
72?????nodeToInsert->key?=?value;
73?????nodeToInsert->next?=?NULL;
74?????p->next?=?nodeToInsert;????
75?}
76?int?_tmain(int?argc,?_TCHAR*?argv[])
77?{
78???????LinkList?list?=?(ListNode?*)malloc(sizeof(struct?Node));
79???????list->next?=?NULL;
80????????insertElement(&list,49);
81????????insertElement(&list,38);
82????????insertElement(&list,65);
83????????insertElement(&list,97);
84????????insertElement(&list,76);
85????????insertElement(&list,13);
86????????insertElement(&list,27);
87????????insertElement(&list,49);
88????????printf("List?before?sort:?");
89????????printList(&list);
90????????listInsertSort(&list);
91????????printf("List?after??sort:?");
92????????printList(&list);
93?????return?0;
94?}

運(yùn)行結(jié)果：

?List before sort: 49 38 65 97 76 13 27 49?

List after ?sort: 13 27 38 49 49 65 76 97?

?

4.Shell排序算法?

?1?//?shellSort.cpp:?主項(xiàng)目文件。
?2?
?3?#include?"stdafx.h"
?4?#include?<stdio.h>
?5?
?6?using?namespace?System;
?7?
?8?void?shellSort(int*?sortArray,?int?size,int?d)
?9?{
10?????int?i,?j,?increment,?temp;
11?????for(increment?=?d;?increment?>?0;?increment?/=?2)
12?????{
13?????????for(i?=?increment;?i?<?size;?i++)
14?????????{
15?????????????temp?=?sortArray[i];
16?????????????j?=?i?-?increment;
17?????????????while(j?>=?0?&&?temp?<?sortArray[j])
18?????????????{
19?????????????????sortArray[j?+?increment]?=?sortArray[j];
20?????????????????j?-=?increment;
21?????????????}
22?????????????sortArray[j?+?increment]?=?temp;
23?????????}
24?????}
25?}
26?
27?void?printArray(int?arrayToPrint[],int?size)
28?{
29????????for(int?i?=?0;?i?<?size;?i++)
30?????{
31?????????printf("%d?",?arrayToPrint[i]);
32?????}
33?????printf("\n");
34?}
35?
36?int?main(array<System::String?^>?^args)
37?{
38?????int?sortArray[8]?=?{49,38,65,97,13,76,27,49};
39?????printf("Array?before?sort:?");
40?????printArray(sortArray,?8);
41?????shellSort(sortArray,?8,?4);
42?????printf("Array?after?sort:??");
43?????printArray(sortArray,?8);
44?????return?0;
45?}

運(yùn)行結(jié)果：

Array before sort: 49 38 65 97 13 76 27 49?

Array after sort: ?13 27 38 49 49 65 76 97?

?

?

?

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/LarmanYuan/archive/2009/06/28/1512822.html

總結(jié)

以上是生活随笔為你收集整理的数据结构-排序（插入排序）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。