c语言的几个算法排序

《c语言的几个算法排序》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、算法排序http://blog.csdn.net/xiajun07061225/article/details/6898246下面简要总结了常用的一些排序算法。如有错误，还请大家指正、见谅~~谢谢~~【1】插入排序：是一个对少量元素进行排序的有效算法。实现比较简单。时间复杂度：O(n^2)，空间复杂度：O(1)。是稳定的排序方法。代码：viewplaincopytoclipboardprint?1.//insertion sort  2.#include   3.using n

2、amespace std;  4.  5.//insertion sort  6.void InsertionSort(int *a,int n)  7.{  8.    int temp;  9.    for(int i = 1;i < n;++i)  10.    {  11.        temp = *(a + i);  12.        int j = i - 1;  13.        while(j >= 0 && *(a + j) > temp)  14.        

3、{  15.            *(a + j + 1) = *(a + j);  16.            --j;  17.        }  18.        *(a + j + 1) = temp;  19.    }  20.}  21.  22.int main()  1.{  2.    int n,temp;  3.    cout<<"please input the number of the values that need to sort:"<

4、4.    cin>>n;  5.    int *a = (int*)malloc(n * sizeof(int));  6.    cout<<"please input each value:"<>temp;  10.        *(a + i) = temp;  11.    }  12.    /* 13.    //insertion sort 14.   

5、 for(int i = 1;i < n;++i) 15.    { 16.        temp = *(a + i); 17.        int j = i - 1; 18.        while(j >= 0 && *(a + j) > temp) 19.        { 20.            *(a + j + 1) = *(a + j); 21.            --j; 22.        } 23.        *(a + j + 1) = temp; 

6、24.    }*/  25.    InsertionSort(a,n);  26.  27.    cout<<"the values after sort:"<

7、方是：在查找插入位置的时候可以采用二分查找，但是这样依然不可以把时间复杂度降低为O(nlogn)，因为移动元素的复杂度没有降低。所以时间复杂度仍然是O(n^2)。做此改进需要添加函数InsertLoc用于二分查找需要插入的位置，以及修改函数InsertionSort的实现。具体如下：viewplaincopytoclipboardprint?1.//改进：用二分查找来找到插入的位置  2.//在数组a[low]---a[high]查找val插入的位置  3.int InsertLoc(int *a

8、,int low,int high,int val)  4.{  5.    if(low == high)  1.    {  2.        if(val > *(a + low))return (low + 1);  3.        else  4.            return low;  5.    }  6.    int mid = (low + high) / 2;  7.    if(val > *(a + mid) && val > *(a + m