希尔堆快排

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);