希尔堆快排
1、希尔排序
(1)、算法思想：希尔排序是插入排序的改良算法，增加了一个步长step，每次插入排序使步长为step的元素形成一个递增序列，然后缩小增量，继续插入，直至step=1时，就是插入排序了，此时排序完成；
算法模型：
(2)、代码实现
#include<stdio.h>
void insertSort(int *a, int count, int step);
void showArray(int *a, int count);
void shellSort(int *a, int count);
void shellSort(int *a, int count){
int step;
for(step = count/2; step > 0; step /= 2){
insertSort(a, count, step);
}
}
void showArray(int *a, int count){
int i;
for(i = 0; i < count; i++){
printf("%d ", a[i]);
}
printf("\n");
}
//以下就是插入排序了，思想完全一样，只不过步长为step而已！！！
void insertSort(int *a, int count, int step){
int i;
int j;
int n;
int tmp;
for(i = step; i < count; i+=step){
tmp = a[i];
for(j = 0; a[i]>a[j] && j<i; j+=step){
;
}
if(i != j){
for(n = i; n > j; n-=step){
a[n] = a[n-step];
}
a[j] = tmp;
}
}
}
void main(void){
int a[] = {2, 7, 1, 11, 0, 9, 8, 10};
int count = sizeof(a)/sizeof(int);
printf("排序前输出如下: ");
showArray(a, count);
shellSort(a, count);
printf("排序后输出如下: ");
showArray(a, count);
}
(3)、结果截图
(4)、算法分析
时间复杂度为：O(nlogn);
2、堆排
(1)、算法思想：对无序数组先构建小堆(完全二叉树结构)，每次删除堆顶元素(用最后一个元素直接覆盖第一个元素)，每次输出堆顶元素就行；
小堆：根(父)结点比左右孩子都小的数字；
(2)、代码实现
#include<stdio.h>
void heapSort(int *a, int count);
void siftDown(int *a, int count, int start);
void swap(int *a, int *b);
int removeHeap(int *a, int n);
int removeHeap(int *a, int n){
int key = a[0];
a[0] = a[n];
siftDown(a, n, 0);
return key;
}
void swap(int *a, int *b){
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
void siftDown(int *a, int count, int start){
int i = start;
int j = 2*i+1;
while(j < count){ //说明有左子树
if(j < count-1 && a[j] > a[j+1]){ //表示存在右孩子的情况下；
j++; //j：表示指向左右子树中最小的一个
}
if(a[i] <= a[j]){
break; //不用调整，父节点的值是最小的；
}else{
swap(&a[i], &a[j]);
//交换
i = j; //一直往树下交换，一直调整到叶子结点
j = 2*i+1;
}
}
}
void heapSort(int *a, int count){
int curPos = count/2-1; //最后一个非叶子结点
int i;
int key;
while(curPos >= 0){
siftDown(a, count, curPos);
curPos--;
}
/* 输出构建好的堆结构
for(i = 0; i < count; i++){
printf("%d ", a[i]);
}
printf("\n");
*/
for(i = 0; i < count; i++){
key = removeHeap(a, count-i-1); //传参：第二个参数是下标
printf("%d ", key);
}
printf("\n");
}
void main(void){
int a[] = {3, 5, 7, 1, 4, 2, 9, 10};
int count = sizeof(a)/sizeof(int);
heapSort(a, count);
}
(3)、结果截图
(4)、算法分析
时间复杂度：O(nlogn);
3、快速排序
(1)、算法思想：分治的思想，一轮下来将第一个数放到了数字大小的中间，经过多次递归完成排序算法；
(2)、代码实现
#include<stdio.h>
int oneQuickSort(int *a, int i, int j);
void quickSort(int *a, int i, int j);
void showArray(int *a, int count);
void showArray(int *a, int count){
int i;
for(i = 0; i < count; i++){
printf("%d ", a[i]);
}
printf("\n");
}
void quickSort(int *a, int i, int j){
int index;
if(i < j){
index = oneQuickSort(a, i, j);
quickSort(a, i, index-1);
quickSort(a, index+1, j);
}
}
int oneQuickSort(int *a, int i, int j){
int tmp;
tmp = a[i];
while(i < j){
while(i < j && a[j] > tmp){
j--;
}
if(i < j){
a[i++] = a[j];
}
while(i < j && a[i] < tmp){
i++;
}
if(i < j){
a[j--] = a[i];
}
}
a[i] = tmp;
return i;
}
void main(void){
int a[] = {3, 7, 1, 0, 9, -9,};
int count = sizeof(a)/sizeof(int);
quickSort(a, 0, count-1);
showArray(a, count);
}
(3)、结果截图
(4)、解法二代码实现
#include<stdio.h>
int quickSortOne(int *a, int count){
int i = 0;
int j;
int tmp;
if(a[0] > a[1]){
tmp = a[0];
a[0] = a[1];
a[1] = tmp;
}
for(j = 2; j < count; j++){
if(a[j] < a[0]){
tmp = a[j];
a[j] = a[++i];
a[i] = tmp;
}
}
tmp = a[0];
a[0] = a[i];
a[i] = tmp;
return i;
}
void quickSort(int *a, int count){
int index = 0;
if(index < count-1){
index = quickSortOne(a, count);
quickSort(a, index+1);
quickSort(a+index+1, count-index-1);
}
}
void showArray(int *a, int count){
int i;
for(i = 0; i < count; i++){
printf("%d ", a[i]);
}
printf("\n");
}
int main(void){
int a[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
int count = sizeof(a)/sizeof(int);
int index;
quickSort(a, count);
showArray(a, count);
return 0;
}
(5)、算法分析
时间复杂度：O(nlogn);
最坏情况：已经排好序或完全逆序，此时时间复杂度：O(n^2);
