数据结构排序算法 (二)

void InsertSort(int arr[],int n)
{
for (int i = 1; i < n; ++i)
{
int tmp = arr[i];
int j;
for (j = i; j > 0 && arr[j-1] > tmp ; --j)
{
arr[j] = arr[j-1];
}
arr[j] = tmp;
}
}

int main(int argc, char const *argv[])
{
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
int len = sizeof(arr)/sizeof(int);
for (int i = 0; i < len; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");

InsertSort(arr,len);

for (int i = 0; i < len; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}希尔排序：
希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。

算法步骤：
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2

时间复杂度：
希尔排序的时间复杂度与增量序列的选取有关，例如希尔增量时间复杂度为O(n^2)，而Hibbard增量的希尔排序的时间复杂度为O(N^(5/4))，但是现今仍然没有人能找出希尔排序的精确下界。

空间复杂度：
希尔排序只有需要一个临时变量存储将要插入的数据，因此空间复杂度为o(1)。

算法稳定性：
由于进行了多次直接插入排序，我们知道一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。

[cpp]
#include


void ShellSort1(int arr[],int n)
{
/*步长为gap，每次排序后gap减半，知道gap =1 */
for (int gap = n/2; gap > 0; gap /= 2)
{
/*对各组进行排序*/
for (int i = gap; i < n; ++i)
{
int j;
int tmp = arr[i];
for (j = i; j >= gap && arr[j - gap] > tmp; j -= gap)
{
arr[j] = arr[j - gap];
}
arr[j] = tmp;
}
}


}


void ShellSort2(int arr[],int n)
{
/*步长为gap，每次排序后gap减半，知道gap =1 */
for (int gap = n/2; gap > 0; gap /= 2)
{
/*对各组进行排序*/
for (int i = gap; i < n; ++i)
{
int j;
int tmp = arr[i];
for (j = i; j >= gap && arr[j -gap] > tmp; j -= gap)
{
arr[j] = arr[j - gap];
arr[j -gap] = tmp ;
}

}
}


}


int main(int argc, char const *argv[])
{
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
int len = sizeof(arr)/sizeof(int);
for (int i = 0; i < len; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");


ShellSort1(arr,len);


for (int i = 0; i < len; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");


return 0;
}

#include

void ShellSort1(int arr[],int n)
{
/*步长为gap，每次排序后gap减半，知道gap =1 */
for (int gap = n/2; gap > 0; gap /= 2)
{
/*对各组进行排序*/
for (int i = gap; i < n; ++i)
{
int j;
int tmp = arr[i];
for (j = i; j >= gap && arr[j - gap] > tmp; j -= gap)
{
arr[j] = arr[j - gap];
}
arr[j] = tmp;
}
}

}

void ShellSort2(int arr[],int n)
{
/*步长为gap，每次排序后gap减半，知道gap =1 */
for (int gap = n/2; gap > 0; gap /= 2)
{
/*对各组进行排序*/
for (int i = gap; i < n; ++i)
{
int j;
int tmp = arr[i];
for (j = i; j >= gap && arr[j -gap] > tmp; j -= gap)
{
arr[j] = arr[j - gap];
arr[j -gap] = tmp ;
}

}
}

}

int main(int argc, char const *argv[])
{
int arr[10] = {9,8,7,6,5,4,3,2,1,0};
int len = sizeof(arr)/sizeof(int);
for (int i = 0; i < len; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");

ShellSort1(arr,len);

for (int i = 0; i < len; ++i)
{
printf("%d ", arr[i]);
}
printf("\n");

return 0;
}

简单选择排序：
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

算法步骤：
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
1.初始状态：无序区为R[1..n]，有序区为空。
2.第1趟排序在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

3.第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

时间复杂度：
选择排序的交换操作介于 0 和 (n - 1） 次之间。选择排序的