几种常用的排序算法比较-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

几种常用的排序算法比较

知与谁同 2018-07-20 10:01:27 916
几种常用的排序算法比较
常用的排序 常用的排序算法 常用的算法 常用算法算法 c/c常用算法
分享到
取消 提交回答
全部回答(2)
  • 沉默术士
    2019-07-17 22:49:37
    还是快速排序的比较好,网上有这个视频,各个排序效率视频
    0 0
  • 云篆
    2019-07-17 22:49:37
    排序,从小大,0坐标的在下面,即排序后小的在下面,大的在上面。

    1,冒泡Bubble:从第0个开始,一直往上,与相邻的元素比较,如果下面的大,则交换。
    Analysis:
    Implementation:
    void BubbleSort(int *pData, int iNum)

    2,插入Insertion:与打扑克牌时整理牌很想象,假定第一张牌是有序的,从第二张牌开始,拿出这张牌来,往下比较,如果有比这张牌大的,则把它拨到上一个位置,直到找到比手上的这张更小的(或到顶了),
    则把手上的这张牌插入到这张更小的牌的后面。
    Analysis:
    Implementation:
    void InsertionSort(int *list, int length)
    {
    int i, j, temp;
    for (i = 1; i < length; i++)
    {
    temp = list[i];
    j = i - 1;
    while ((j >= 0) && (list[j] > temp))
    {
    list[j+1] = list[j];
    j--;
    }
    list[j+1] = temp;
    }
    }

    3,选择Selection:从所有元素中找到最小的放在0号位置,从其它元素(除了0号元素)中再找到最小的,放到1号位置,......。
    Analysis:
    Implementation:
    void SelectionSort(int data[], int count)
    {
    int i, j, min, temp;
    for (i = 0; i < count - 1; i++)
    {
    /* find the minimum */
    min = i;
    for (j = i+1; j < count; j++)
    {
    if (data[j] < data[min])
    {
    min = j;
    }
    }
    /* swap data[i] and data[min] */
    temp = data[i];
    data[i] = data[min];
    data[min] = temp;
    }
    }

    4,快速Quick:先拿出中间的元素来(值保存到temp里),设置两个索引(index or pointer),一个从0号位置开始往最大位置寻找比temp大的元素;一个从最大号位置开始往最小位置寻找比temp小的元素,找到了或到顶了,则将两个索引所指向的元素
    互换,如此一直寻找交换下去,直到两个索引交叉了位置,这个时候,从0号位置到第二个索引的所有元素就都比temp小,从第一个索引到最大位置的所有元素就都比temp大,这样就把所有元素分为了两块,然后采用前面的办法分别排序这两个部分。总的来
    说,就是随机找一个元素(通常是中间的元素),然后把小的放在它的左边,大的放右边,对左右两边的数据继续采用同样的办法。只是为了节省空间,上面采用了左右交换的方法来达到目的。
    Analysis:
    Implementation:
    void QuickSort(int *pData, int left, int right)
    {
    int i, j;
    int middle, iTemp;
    i = left;
    j = right;

    middle = pData[(left + right) / 2]; //求中间值
    do
    {
    while ((pData[i] < middle) && (i < right)) //从左扫描大于中值的数
    i++;

    while ((pData[j] > middle) && (j > left)) //从右扫描小于中值的数
    j--;

    if (i <= j) //找到了一对值
    {
    //交换
    iTemp = pData[i];
    pData[i] = pData[j];
    pData[j] = iTemp;
    i++;
    j--;
    }
    } while (i <= j); //如果两边扫描的下标交错,就停止(完成一次)

    //当左边部分有值(left<j),递归左半边
    if(left < j)
    QuickSort(pData, left, j);

    //当右边部分有值(right>i),递归右半边
    if(right > i)
    QuickSort(pData, i, right);
    }

    5,希尔Shell:是对Insertion Sort的一种改进,在Insertion Sort中,从第2个位置开始取出数据,每次都是与前一个(step/gap==1)进行比较。Shell Sort修改为,在开始时采用较大的步长step,
    从第step位置开始取数据,每次都与它的前step个位置上的数据进行比较(如果有8个数据,初始step==4,那么pos(4)与pos(0)比较,pos(0)与pos(-4),pos(5)与pos(1),pos(1)与pos(-3),
    ...... pos(7)与pos(3),pos(3)与pos(-1)),然后逐渐地减小step,直到step==1。step==1时,排序过程与Insertion Sort一样,但因为有前面的排序,这次排序将减少比较和交换的次数。
    Shell Sort的时间复杂度与步长step的选择有很大的关系。Shell排序比冒泡排序快5倍,比插入排序大致快2倍。Shell排序比起QuickSort,MergeSort,HeapSort慢很多。但是它相对比较简单,它适合
    于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。
    Analysis:
    Implementation:
    template<typename RandomIter, typename Compare>
    void ShellSort(RandomIter begin, RandomIter end, Compare cmp)
    {
    typedef typename std::iterator_traits<RandomIter>::value_type value_type;
    typedef typename std::iterator_traits<RandomIter>::difference_type diff_t;

    diff_t size = std::distance(begin, end);
    diff_t step = size / 2;
    while (step >= 1)
    {

    for (diff_t i = step; i < size; ++i)
    {
    value_type key = *(begin+i);
    diff_t ins = i; // current position

    while (ins >= step && cmp(key, *(begin+ins-step)))
    {
    *(begin+ins) = *(begin+ins-step);
    ins -= step;
    }

    *(begin+ins) = key;
    }

    if(step == 2)
    step = 1;
    else
    step = static_cast<diff_t>(step / 2.2);
    }
    }

    template<typename RandomIter>
    void ShellSort(RandomIter begin, RandomIter end)
    {
    typedef typename std::iterator_traits<RandomIter>::value_type value_type;
    ShellSort(begin, end, std::less<value_type>());
    }

    6,归并Merge:先将所有数据分割成单个的元素,这个时候单个元素都是有序的,然后前后相邻的两个两两有序地合并,合并后的这两个数据再与后面的两个合并后的数据再次合并,充分前面的过程直到所有的数据都合并到一块。
    通常在合并的时候需要分配新的内存。
    Analysis:
    Implementation:
    void Merge(int array[], int low, int mid, int high)
    {
    int k;
    int *temp = (int *) malloc((high-low+1) * sizeof(int)); //申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
    int begin1 = low;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = high;

    for (k = 0; begin1 <= end1 && begin2 <= end2; ++k) //比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
    {
    if(array[begin1]<=array[begin2])
    {
    temp[k] = array[begin1++];
    }
    else
    {
    temp[k] = array[begin2++];
    }
    }
    if(begin1 <= end1) //若第一个序列有剩余,直接拷贝出来粘到合并序列尾
    {
    memcpy(temp+k, array+begin1, (end1-begin1+1)*sizeof(int));
    }
    if(begin2 <= end2) //若第二个序列有剩余,直接拷贝出来粘到合并序列尾
    {
    memcpy(temp+k, array+begin2, (end2-begin2+1)*sizeof(int));
    }
    memcpy(array+low, temp, (high-low+1)*sizeof(int));//将排序好的序列拷贝回数组中
    free(temp);
    }

    void MergeSort(int array[], unsigned int first, unsigned int last)
    {
    int mid = 0;
    if (first < last)
    {
    mid = (first+last)/2;
    MergeSort(array, first, mid);
    MergeSort(array, mid+1,last);
    Merge(array,first,mid,last);
    }
    }
    0 0
添加回答
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

相似问题
最新问题