經常使用排序算法整頓分享(疾速排序算法、希爾排序)。本站提示廣大學習愛好者:(經常使用排序算法整頓分享(疾速排序算法、希爾排序))文章只能為提供參考,不一定能成為您想要的結果。以下是經常使用排序算法整頓分享(疾速排序算法、希爾排序)正文
整頓了幾個排序算法,經由過程測試來看,最快的照樣疾速排序算法,的確不是一個數目級的速度。
#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;
}