三、希尔排序
希尔排序也是插入排序的一种，它先将整个数列分割成若干个小的子序列进行插入排序，逐渐减少子序列的个数，直到最后组合成一个数列，完成整个排序过程。希尔排序的过程使用文字描述可以表示为如下几步：
1.假设数列元素个数为n，先取一个小于n的增量d1，将所有间隔d1距离的元素放为1组进行插入排序，d1通常取值n/2，向下取整。
2.再次取d2<d1，将所有间隔d2距离的元素放为1组进行插入排序，通常d2取值为d1/2，向下取整。
3.重复步骤2，直到取得d等于1。
图示希尔排序如下：
JavaScript实现的希尔排序：
var array = [1,54,2,64,12,65,76,46,34,98];
//希尔排序
//步长 分组数
var d = Math.floor(array.length/2);
while(d>=1){
//每组元素个数
var counts = Math.floor(array.length/d);
//每组排序依次
for (var i = 0; i < d ; i++) {
//组内的插入排序
for(var j = 0;j<counts-1;j++){
var temp = array[(j+1)*d];
for(var k = ((j+1)*d);k>0;k-=d){
if (temp<array[k]) {
array[k+d] = array[k];
array[k] = temp;
}
}
}
}
//重取d值
d=Math.floor(d/2);
}
console.log(array);//[ 1, 2, 12, 34, 46, 54, 64, 65, 76, 98 ];
C实现的希尔排序：
#include <stdio.h>
//希尔排序
void mySort(int array[],int size){
int d = size/2;
while(d>=1){
//每组元素个数
int counts = size/d;
//每组排序依次
for (int i = 0; i < d ; i++) {
//组内的插入排序
for(int j = 0;j<counts-1;j++){
int temp = array[(j+1)*d];
for(int k = ((j+1)*d);k>0;k-=d){
if (temp<array[k]) {
array[k+d] = array[k];
array[k] = temp;
}
}
}
}
//重取d值
d=d/2;
}
}
int main(){
int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98 };
mySort(a,10);
for(int i = 0;i<10;i++){
printf("%d\n",a[i]);
}
return 0;
}
四、选择排序
前边所说的3种排序算法原理上都是插入排序，即从无序数列中逐个取元素将其插入到有序数列中的合适位置。选择排序则刚好与之相反，其从无序数列中先找到最小值，放在排序数列首部，在依次找到剩余数列的中最小值追加入有序数列，最终完成数列的排序。用文字描述选择排序步骤不如：
1.找到数列中的最小值，将其作为有序数列的第一个元素。
2.从剩余数列中找到最小值，追加入有序数列。
3.重复步骤2，直到排完整个数列。
图示描述选择排序如下：
JavaScript实现的选择排序算法：
var array = [1,54,2,64,12,65,76,46,34,98];
//选择排序
for(var i=0;i<array.length-1;i++){
//找到最小值
var min = array[i];
var index = i;
for (var j = i+1; j <array.length; j++) {
if (array[j]<min) {
min = array[j];
index = j;
}
}
//进行交换
array[index]=array[i];
array[i]=min;
}
console.log(array);//[ 1, 2, 12, 34, 46, 54, 64, 65, 76, 98 ]
C实现的选择排序算法：
//选择排序
void mySort(int array[],int size){
for(int i=0;i<size-1;i++){
int min = array[i];
int index = i;
for(int j=i+1;j<size;j++){
if(array[j]<min){
min = array[j];
index = j;
}
}
array[index] = array[i];
array[i]=min;
}
}
int main(){
int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98};
mySort(a,11);
for(int i = 0;i<10;i++){
printf("%d\n",a[i]);
}
return 0;
}
五、冒泡排序
冒泡排序和选择排序是我们学习编程课时必不可少的两种排序算法，冒泡排序算法的核心是每次比较相邻的连个元素，如果它们的顺序不对，则进行交换，一轮排序下来，最大值一定被排序到数列的末端。之后除去最后一个元素再进行第二轮冒泡，直到整个数列排序完成。用文字描述冒泡排序的过程如下：
1.从左向右依次比较相邻两元素，如果顺序不对，则进行交换，最终最大的元素被放在最后。
2.除去最后一个元素，重复步骤1，最终剩下元素中最大的被放在倒数第2个位置。
3.继续上面的重复，直到排完整个数列。
JavaScript实现的冒泡排序算法：
var array = [1,54,2,64,12,65,76,46,34,98];
//冒泡排序
for(var i=0;i<array.length-1;i++){
for(var j=0;j<array.length-i-1;j++){
var temp = array[j];
if (temp>array[j+1]) {
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
console.log(array);//[ 1, 2, 12, 34, 46, 54, 64, 65, 76, 98 ]
C实现的冒泡排序算法：
#include <stdio.h>
//冒泡排序
void mySort(int array[],int size){
for(int i =0;i<size-1;i++){
for(int j=0;j<size-1-i;j++){
int temp = array[j];
if(temp>array[j+1]){
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
int main(){
int a[] = {1, 2, 12, 34, 46, 54, 64, 65, 76, 98};
mySort(a,10);
for(int i = 0;i<10;i++){
printf("%d\n",a[i]);
}
return 0;
}
