插入排序
插入排序基于这样一种情况，待插入的数组是顺序的(升序或降序)，此时将插入数据从数组从后向前比较，满足条件就插入，不满足就依次向后移动
插入排序就好象玩扑克时一张一张的拿牌，大的在左边，小的在右边，每拿一张牌就从右到左一次比较，在第一张大于的牌的右边插入新的扑克
插入算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| typedef int ElementType;
void insertSort(ElementType* array,int len){
int arrayMaxIndex = len - 1;
int arrayMinIndex = 0;
int index = 0;
int j = 0;
for(index = arrayMinIndex + 1;index <= arrayMaxIndex;index++){
int insertValue = array[index];
for(j = index - 1;j >= 0 && array[j] > insertValue;j--){
array[j + 1] = array[j];
}
array[j + 1] = insertValue;
}
}
|
希尔排序
希尔排序通过比较相距一定间隔的元素来工作，将比较的元素按照大小排列到比较元素的位置，然后通过减小间隔再次比较，最后间隔为1时所有比较完成
最上面数据为未排序数据，由上往下增量依次为 5,3,1
希尔排序算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| typedef int ElementType;
void shellSort(ElementType* array,int increment,int len){
int arrayMinIndex = 0;
int arrayMaxIndex = len - 1;
int sortTime = 0;
int j = 0;
int insertValue = 0;
if(increment > len){
shellSort(array,1,len);
}
for(;sortTime < increment;sortTime++){
for(int i = sortTime + increment;i < len;i += increment){
insertValue = array[i];
for(j = i - increment;j >= arrayMinIndex && array[j] >= insertValue;j -= increment){
array[j + increment] = array[j];
}
array[j + increment] = insertValue;
}
}
}
|
参考源码