程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 經常使用排序算法整頓分享(疾速排序算法、希爾排序)

經常使用排序算法整頓分享(疾速排序算法、希爾排序)

編輯:關於C++

經常使用排序算法整頓分享(疾速排序算法、希爾排序)。本站提示廣大學習愛好者:(經常使用排序算法整頓分享(疾速排序算法、希爾排序))文章只能為提供參考,不一定能成為您想要的結果。以下是經常使用排序算法整頓分享(疾速排序算法、希爾排序)正文


整頓了幾個排序算法,經由過程測試來看,最快的照樣疾速排序算法,的確不是一個數目級的速度。


#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <time.h>
#include <unistd.h>

//一些排序算法整頓
//拔出排序算法
//直接拔出排序
void
direct_insert_sort(int *a,int len)
{
 //思緒:最初一個順次和後面的停止比擬
 //將知足的前提的往後挪動,固然是從頭
 //開端且是從最小比擬數組開端逐步擴展
 //到全部數組
 int i,j,temp;
 for(i = 1;i < len;++i) {
  //獲得最初一個索引數據
  temp = a[i];
  for(j = i - 1;j >= 0;--j) {
   //從倒數第二個開端
   if(a[j] > temp)//升序分列
    a[j + 1] = a[j];
   else
    break;//連忙加入
  }
  //將最初一個地位拔出到適合的地位
  a[j + 1] = temp;
 }
}

//希爾排序
void
shell_insert_sort(int *a,int len)
{
 //思緒:就是比直接拔出排序多了層
 //輪回,這層輪回是用來掌握步進按
 //照算法的原來思緒是如許可以削減
 //交流次數
 int i,j,h,temp;
 for(h = len / 2;h > 0;h /= 2) {
  //內層其實實質照樣直接拔出
  //算法思緒
  //留意下i += h和i++二者對算
  //法的影響
  for(i = h;i < len;i += h) {
   //獲得最初一個索引的值
   temp = a[i];
   for(j = i - h;j >= 0;j -= h) {
    if(a[j] > temp)//升序分列
     a[j + h] = a[j];
    else
     break;
   }
   //將找到的地位拔出最初一個索引
   a[j + h] = temp;
  }
 }
}

//選擇排序
//冒泡排序
void
bubble_swap_sort(int *a,int len)
{
 //思緒:從數組最初開端兩兩比擬
 //將底層知足請求的數據逐步交流
 //到下層,能夠招致交流次數太多
 int i,j,temp;
 //假如一次冒泡中沒有產生交流可
 //以以為此次分列曾經停止
 bool exchange = false;
 for(i = 0;i < len - 1;++i) {
  for(j = len - 1;j > i;--j) {
   //知足前提的就停止交流
   if(a[j] < a[j - 1]) {
    temp = a[j];
    a[j] = a[j - 1];
    a[j - 1] = temp;
    exchange = true;
   }
  }
  if(exchange)
   exchange = false;
  else
   break;
 }
}

//疾速排序
void
quick_swap_sort(int *a,int low,int high)
{
 //思緒:從數組中找一個值
 //然後分列數組使其雙方要
 //麼年夜於要末小於這個值,
 //然後遞歸下去排序
 //優勢在於每次找中央值可
 //以交流許多次。
 int _low,_high,qivot;
 if(low < high) {
  _low = low;
  _high = high;
  //這裡從最初一個開端
  qivot = a[low];
  //找中央值的方法就是逐步切近親近
  //從頭尾兩頭開端切近親近,趁便也
  //排序了
  while(_low < _high) {
   //既然是從low開端,那末起首
   //就從high找小於qivot的(升
   //序分列)
   while(_low < _high && a[_high] > qivot)
    --_high;//逐步向中央切近親近
   if(_low < _high)//必定是找到了a[_high] > qivot的情形
    a[_low++] = a[_high];
   //這下a[_high]空出地位來了,所以從low找
   //比qivot年夜的數據
   while(_low < _high && a[_low] < qivot)
    --_low;//切近親近中央
   if(_low < _high)
    a[_high--] = a[_low];
  }
  //最初_low == _high那末這個地位就是qivot的地位
  a[_low] = qivot;
  //遞歸下去
  quick_swap_sort(a,low,_high - 1);
  quick_swap_sort(a,_low + 1,high);
 }
}

//選擇排序
//直接選擇排序
void
direct_select_sort(int *a,int len)
{
 //思緒:就是遍歷數組找到極值
 //放到頭或許尾,如許逐步減少
 //規模到最小比擬數組
 int i,j,pos,temp;
 for(i = 0;i < len - 1;++i) {
  //從頭開端獲得一個值假定為極值
  pos = i;
  for(j = i + 1;j < len;++j) {
   //知足前提
   if(a[pos] > a[j])//升序
    pos = j;
  }
  if(pos != i) {
   //停止交流
   temp = a[pos];
   a[pos] = a[i];
   a[i] = temp;
  }
 }
}

void
disp(int *a,int len)
{
 int i = 0;
 for(;i < len;i++) {
  if(i != 0 && i % 16 == 0)
   printf("\n");
  printf(" %d",a[i]);
 }
 printf("\n");
}

#define TEST_ARRAY_LEN 100000
#define TEST_COUNT 1

int
main(int argc,char *argv[])
{
 //int a[] = {1,8,4,0,9,6,3,7,2,18,74,5,64,12,39};
 //int len = sizeof(a) / sizeof(a[0]);
 //direct_insert_sort(a,len);
 //shell_insert_sort(a,len);
 //bubble_swap_sort(a,len);
 //quick_swap_sort(a,0,len - 1);
 //direct_select_sort(a,len);
 disp(a,len);

 return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved