寫的比快排速度快的演算法，有人給看看嗎？

12-31

數據個數:30000000
QsTime:16162
Mytime:7098
結果一致

數據個數:3000000
QsTime:1685
Mytime:749
結果一致
數據個數:300000
QsTime:156
Mytime:109
結果一致

以上是與c語言自帶的快速排序比較的結果。
源碼如下:
// 排序.cpp : 定義控制台應用程序的入口點。 //
#include "stdafx.h" #include & #include & #define _AFXDLL #include & #include & using namespace std; #define buf_length 30000000 int an[buf_length]; int bn[buf_length]; #define all_count 1000 struct data { int last; int value; }; struct buf { int lasts[all_count]; data d[buf_length]; int cc[all_count]; int all_c; inline void reset(int val,int allc) { all_c=0; for (int i=0;i&max) max=a[i]; if(a[i]&all_c-1?all_c-1:z; z=z&<0?0:z; buffer.push(z,a[i]); } int p=start; for (int i=0;i&1) sort(a,start,zm[0]); } else { if(zm[i]-zm[i-1]&1) sort(a,zm[i-1],zm[i]); } } delete zm; }; inline int cmp ( const void *a , const void *b ) { return *(int *)a - *(int *)b; } int _tmain(int argc, _TCHAR* argv[]) { srand(time(0)); int zz=buf_length; cout&<&<"數據個數:"&<&



本質上來說這就是個桶排序嘛，按值的範圍分1000個桶，只是大桶裡面又細分了小桶，桶排序是依賴於被排序的值的類型的，不算是通用排序，跟快排比較也沒啥意義；而且你這個也佔了測試數據的優勢，首先rand()的範圍就很小，一般是0-32767，這樣數很多的時候就有大量是重複的；第二因為是均勻分布，所以每個桶裡面的數值都分得差不多。你可以試試改用int64範圍的數值（或者double），然後排一個等比數列
x越大，分布越不均勻，桶排序的效果也會越差，可以驗證一下試試（最好是用浮點數）。
你這個演算法雖然貌似是桶排序，但因為桶的數量是固定的，可以說仍然是個O(nlogn)的演算法，甚至沒有一般桶排序的效率高，之所以比快排快那麼一點完全是因為數據範圍的問題。你可以試下直接建一個RAND_MAX大小的數組，然後直接記錄下每個數值出現的次數，最後從小到大按出現次數重新輸出到數組裡，這叫計數排序，比你的演算法快得多，但反正也沒啥意義。

 
app上，不方便看代碼。不過排序演算法基本被研究透了：
1. 比較類型比較排序，最快是(nlgn)*基本代碼執行時間，這是已被數學證明的；
2. 非比較型排序，最快是n*基本代碼執行時間，因為你至少看一去次全部數據才能排序。但這種類型比較快，都是犧牲了一些額外空間去儲存數據信息。
qsort源碼我沒看過，但作為標準庫，應該是效率最高的比較排序。若出現比它快的情況，只可能是：
1. 題主的是比較排序，但比它快，只能是測試數據有利於你的演算法；
2. 題主的是非比較排序。
2016-3-29
謝評論及其他答案提醒, qsort來自經典的C庫&, sort來自STL&. 
qsort採用快速排序演算法
sort是qsort的改進版, 可根據數據採用不同的演算法, 性能更加穩定.

 
1 qsort是C的庫函數，名聲並沒有stl的sort好
2 qsort執行大量cmp函數回調，通過函數指針調用的，你的sort最好也這麼做看看，而且別放一個代碼文件，也做成qsort這種庫的形式
3 匆匆掃了一眼，是結合了桶排吧，這就是兩種演算法的問題了

「比較排序」和「非比較排序」是兩種演算法問題。
例如，試試把你的實現改成字元串字典序排序看看？

qsort慢很正常，你把你的排序的compare也做成函數指針，再和qsort比試試

花式桶排……搞了min(1000, 區間差值+1)個桶……桶排本來就可能比快排快，但是內存消耗太大了
總感覺數據非隨機的時候會退化得很捉急。。。

現在的年輕人都不讀演算法導論了嗎

 
————————————————————
了解到題主不是計算機專業出身，很抱歉。題主已經比大部分計算機專業的學生好很多了，建議參考一下計算機專業所修課程，加強基礎。

以後知乎上問這種問題，我們應該統一邀請題主去做WC2017第二題《挑戰》的任務一。
「WC2017」挑戰 - 題目 - LibreOJ
題意：給定  個 32 位無符號整數，將它們從小到大排序。
數據範圍： 
內存限制2048MB（幾乎無限制）
現場時限3s（機器是i5），各oj限於硬體水平，有所放寬。
您能把這個任務做了，我就相信您的演算法很有價值。
（要麼是演算法本身有價值，要麼是優化得當）

 
通過的代碼 ： 統計 - LibreOJ 
點擊每個人的 【編號】 一欄可以查看代碼。

為什麼大家都是一種「你以為你是誰，動不動就能超過快速排序」的語氣在回答呢？為什麼不說一些能夠幫助題主的建議和意見呢？
我想告訴題主（可能這裡的一些人也能受益）的是：


當我們需要對一堆數據排序的時候，比較排序是一類非常常見的演算法，其中快速排序在很多情況下是最快的且有成熟的函數庫可以直接用。但是，快速排序甚至比較排序不一定是對所有問題都最快的演算法，特定的問題下是有更快的演算法的。
當然，更快的演算法不一定就是更合適的，取決於具體的應用場景。
首先，排序速度真的需要考慮么？10毫秒還是20毫秒如果後面跟著一個10秒的操作，就基本沒差別了。
速度是唯一需要考慮的么？如果在手機上，內存很緊缺，更快的演算法如果需要更多的內存，會是問題么？
從工程上講，如果不使用標準庫自己寫排序演算法是一個很耗費開發資源的事情，除了演算法實現自身，邏輯測試、性能測試、後期維護都會需要佔用不少的開發人力和時間。簡單的說，幾百行代碼替換一行代碼，帶來的收益到底值不值。
回到演算法本身，題主的演算法叫桶排序（Bucket sort），wiki 中文頁面（https://zh.wikipedia.org/wiki/%E6%A1%B6%E6%8E%92%E5%BA%8F）有一些介紹，英文的更詳細一些（Bucket sort），可以仔細閱讀一下。
回到代碼本身

大部分操作符前後加上空格會讓你的代碼好讀很多，比如 =, +-*/&>&<，逗號和分號後面加上一個空格
最好不要用中文的文件名
既然選擇了 C++ 而不是 C，內存之類的就應該讓 vector 之類的類管理起來
「int all_c=all_count;」 這一行的賦值是沒必要的
if/else 後面的主體只有一個語句的時候，還是加上{}，最忌諱的時候兩個主體一個有大括弧一個沒有
沒時間做更多的 code review 了
就純整數排序來說，還有更快更省的數據結構，就是在範圍足夠小的時候桶變成計數器。



void qsort(void*, size_t, size_t, int (*)(const void*, const void*));
你看下 qsort 的介面，這類型擦除「完美」到應付一切數組結構。
再加個 void *(*indexer)(void *base, ptrdiff_t offset) 參數就能應對隨機訪問迭代器了。
但值得注意的就是（一般實現中）這個介面限制了性能。特別是 qsort 作為編譯後二進位代碼的情況下。

 
比較函數作為回調函數出現，每次都調用函數指針，而且無法優化掉調用開銷。對象交換需要用類似 memcpy 或 memmove 的功能，它們需要處理對齊；或者直接逐位元組交換。
主流實現中， qsort 的演算法是錘鍊過的。但因為介面要求，編譯器終究是少了很多優化機會。
為單個類型手寫快排的話，對象定址、比較、交換都會比 qsort 中的快不止一點，而且更容易優化。
如果把手寫的工作再用模板或宏簡化，就等於做出大半個 std::sort 了。
另外，題主有沒有考慮過泛型化的桶排序應該是怎樣的？

你先試試跟std::sort比一比
排序演算法的工業級實現是可以寫論文的

且不說內存佔用。當測試數據的取值範圍大於測試數據樣本數量時，桶排比快排慢。
順便推一下我寫的比快排速度快的演算法

 
在數組裡所有數目相同的情況下。我用O(1)的時間就能完成排序。秒殺快排。


睡眠排序好～

====================更新測試結果========================


測試環境，i7 4700hq，@3.4ghz，2x8g內存，win10，64位
release，vs2015，默認的o2優化。
計時我換成了c++11的chrono，單位是ms
於是，此貼終結？PS，大家不要歧視qsort，這個測試里最慢的明明是是rand。。。。

 
還有，這個程序吃了600M內存，我想了想不像是原始數據，也不像是qsort或者stl申請的。那麼題主你這個開銷是不是太大了點啊。。。。
1.qsort存在反覆調用比較函數的問題，不知道現在的編譯器會不會優化。
2.stl的sort，根據數據量不同還會選用不同的排序方法，試試
3.開優化。不然很多可以內聯的函數就會反覆調用增加開銷。
4.就算從演算法複雜度上，理論上你勝過了對方，在計算機上可能你會因為cache miss而落後很多。這個問題，得優化開到最大，然後再profile才知道。
在做完詳盡的測試前，我不敢說不相信你，但也不敢相信你。

1.題主竟然寫出了一個比快排快的排序演算法......就覺得很厲害了...而且題主似乎還覺得qsort就是快排
2.展示演算法為何亂入afx.h
3.C++代碼為何用time.h而不是ctime
4.宏定義常量和全局大數組讓我看著有點方
5.sort居然是這麼老長一個內聯函數
先就這樣吧=_=

1.題主用C++標準庫的sort進行比較。
2.請用隨機數進行排序測試

我非常友好的表示，為毛我有種民科證明哥德巴赫猜想發現引力波的即視感。

快速排序不是算的概率上的平均時間複雜度嗎？樓主有沒有算過平均時間複雜度啊？這些比較演算法的最壞複雜度好像是n2吧。所以樓主拿幾個值比較，令人信服程度不夠啊！如果有數學推到，就更好了（壞笑）。

// 謝......謝邀
先講個笑話吧：
小學六年級的時候，我參加了省里一個小學生信息學競賽，
當時用的是  語言，演算法考的很少，大概約瑟夫問題可以作為壓軸題的那種。
在回去的路上，我突發奇想，想出了跟桶排序類似的排序演算法，
因為當時大家只接觸過冒泡排序，頓時覺得自己非常牛逼，跟全車的人唧唧呱呱講個不停。
直到進了初中之後跟著教練學習了參加NOIP普及組需要的知識，
學會了快速排序，也知道了當時那個想法其實就是桶排序，以及掌握了一些簡單的複雜度分析。
現在在大學裡，學習了演算法設計與分析這門課，也算涉獵了ACM-ICPC競賽。我了解到系統的漸進複雜度分析知識，以及計算理論研究與實際工程實踐的差別。
舉個例子的話，就是C++ STL中快速排序的實現，在理論上知道它是個不穩定排序的情況下如何實現的時候在局部用冒泡、堆排序進行優化以保證其平均複雜度仍然比較優秀。
結論就是：
我現在覺得，大概，那是無知的我最接近一個合格民科的一段時光吧：）

答主不要因為前面的很多回答受打擊，挺不錯的，演算法比較耗內存，換取時間了……比我上學的時候強多了

沒有認真看題主的代碼，不過從評測結果來看，題主的實現並不快。（2底的log10約為3.3）
//------------------------------------------------------------------------------//
話說，經典快排比VC的qsort快一點也不奇怪。


//------------------------------------------------------------------------------//
#include &

#include &

#include &

#include &

#include &

#include &

#include &

#include &

#ifdef __GNUC__

inline static uint64_t Touch(void)

{

	union {

		uint64_t all;

		struct {

			uint32_t low;

			uint32_t high;

		};

	} value;

	asm volatile (

		"rdtsc"

		: "=a" (value.low), "=d" (value.high)

	);

	return value.all;

}

#else

#include &

#define Touch __rdtsc

#endif
static void SimpleSort(int list[], unsigned size)

{

	if (size &< 2) return;
	unsigned best = 0;
	for (unsigned i = 1; i &< size; i++) {
		if (list[i] &< list[best]) {
			best = i;
		}
	}
	std::swap(list[0], list[best]);
	for (unsigned i = 1; i &< size; i++) {
		unsigned pos;
		int num = list[i];
		for (pos = i; list[pos - 1] &> num; pos--) {

			list[pos] = list[pos - 1];

		}

		list[pos] = num;

	}

}
static unsigned Partition(int list[], unsigned size)

{

	int pivot = list[size / 2];	//size &>= 3

	unsigned a = 0, b = size - 1;

	while (true) {

		while (list[a] &< pivot) a++;
		while (list[b] &> pivot) b--;

		if (a &>= b) break;

		std::swap(list[a++], list[b--]);

	}

	return a;

}
void QuickSort(int list[], unsigned size)

{

	if (size &< 16) {
		SimpleSort(list, size);
	} else {
		unsigned line = Partition(list, size);
		QuickSort(list, line);
		QuickSort(list + line, size - line);
	}
}

void Benchmark(
	const std::function&)&> func,

	std::vector& list, const char* msg)

{

	uint64_t start = Touch();

	func(list);

	printf("%s%" PRIu64 "

", msg, Touch() - start);

}
static int Compare(const void* pa, const void* pb)

{

    //BUG： 0 - 0x80...0

    return *(const int*)pa - *(const int*)pb;

}
int main(int argc, char* argv[])

{

    const unsigned size = 3000;

    std::vector& lst1(size);

    std::vector& lst2(size);

    std::vector& lst3(size);
    srand(time(NULL));

    for (unsigned i = 0; i &< size; i++) {
        int num = rand();
        lst1[i] = num;
        lst2[i] = num;
        lst3[i] = num;
    }

    Benchmark([](
        std::vector& list) {

            qsort(list.data(), list.size(), sizeof(int), Compare);

        },

        lst1, "Clib: ");

    Benchmark([](

        std::vector& list) {

            QuickSort(list.data(), list.size());

        },

        lst2, "DIY : ");

    Benchmark([](

        std::vector& list) {

            std::sort(list.begin(), list.end());

        },

        lst3, "STL : ");
    for (unsigned i = 0; i &< size; i++) {
        if (lst1[i] != lst2[i]) {
            puts("bad");
            return 1;
        }
    }
    puts("good");
    return 0;
}


  推薦閱讀：


※Office 2013 的 UI 是什麼語言寫的？
※作為程序員，自己在Github上的項目被很多人使用是什麼體驗？
※消滅星星（Popstar）遊戲是怎麼開發實現的？難不難？
※IEEE 754格式是什麼?
TAG:演算法 | 編程 | 計算機 | C |