void sort(int *a, int len)
{
	for(int i=0; i a[j+1])
			{
				int temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
				flags = false;
			}
		}
		if(flags)break;
	}
}

void sort(int *a, int len)
{
        for(int i=1; i0&&t

ヒルソート

void ShellSort(int array[],int length)
{
	int d = length/2;   //         
	int i, j, temp;
	while(d>=1)
	{
		for(i=d; i=0 && array[j]>temp)
			{
				array[j+d] = array[j];
				j = j-d;
			}
			array[j+d] = temp;
		}
		print(array,length);
		d= d/2;    //    
	}
}

void ShellSort(int *a, int len)
{
	for (int d=len/2; d>=1; d/=2)
	{
		int j, temp;
		for (int i=d; i=0 && a[j]>temp)
			{
				a[j+d] = a[j];
				j -= d;
			}
			a[j+d] = temp;
		}
	}
}

ソートの選択

void sort(int *a, int len)
{
	for(int i=0; i

クイックソート
方法1:

void sort(int *a, int len)
{
        if(len<1) return;
        int L = 0;
        int R = len-1;
        while(L=a[L]) R--;
                swap(a[L], a[R]);
                while(L=a[L]) L++;
                swap(a[L], a[R]);
        }
        sort(a, L);//    ,   L R  
        sort(a+L+1, len-L-1);//    ,     len-1
}

方式二(最適化後、より効率的):

void sort(int *a, int len)
{
        if(len<1) return;
        int L = 0;
        int R = len-1;
        int piv = a[0];
        while(L=piv) R--;
                a[L] = a[R];
                while(L

集計ソート
集計ソートは、集計操作に確立された有効なソートアルゴリズムである.このアルゴリズムは分割法(Divide and Conquer)を用いた非常に典型的な応用である.
まず、2つの整列数列をマージする方法を考えます.これはとても簡単で、2つの数列の最初の数を比較するだけで、誰が小さいかは先に誰を取ります.
取ったら対応数列からこの数を削除します.次に比較を行い、数列が空の場合は、そのまま別の数列のデータを順番に取り出せばよい.

//     a[] b[]   c[] 
void MemeryArray(int a[], int n, int b[], int m, int c[])
{
	int i, j, k;

	i = j = k = 0;
	while (i < n && j < m)
	{
		if (a[i] < b[j])
			c[k++] = a[i++];
		else
			c[k++] = b[j++]; 
	}

	while (i < n)
		c[k++] = a[i++];

	while (j < m)
		c[k++] = b[j++];
}

は、O(n)に達することができる比較的効率が高いことを示している.
上の連結秩序数列問題を解決し,集計並べ替えを見ると,配列を2つのグループA,Bに分けることが基本構想である.
この2つのグループ内のデータが秩序化されている場合、この2つのグループのデータを簡単にソートすることができます.この2つのグループ内のデータを秩序化するにはどうすればいいですか?
A、Bグループをそれぞれ2つのグループに分けることができます.順次類推すると,分割されたグループにデータが1つしかない場合,このグループ内は秩序に達していると考えられる.
そして隣接する2つのグループを統合すればいいです.これにより,再帰的に数列を分解し,数列をマージすることで集計ソートが完了する.

//        a[first...mid] a[mid...last]  。
void mergearray(int a[], int first, int mid, int last, int temp[])
{
	int i = first, j = mid + 1;
	int m = mid,   n = last;
	int k = 0;
	
	while (i <= m && j <= n)
	{
		if (a[i] <= a[j])
			temp[k++] = a[i++];
		else
			temp[k++] = a[j++];
	}
	
	while (i <= m)
		temp[k++] = a[i++];
	
	while (j <= n)
		temp[k++] = a[j++];
	
	for (i = 0; i < k; i++)
		a[first + i] = temp[i];
}
void mergesort(int a[], int first, int last, int temp[])
{
	if (first < last)
	{
		int mid = (first + last) / 2;
		mergesort(a, first, mid, temp);    //    
		mergesort(a, mid + 1, last, temp); //    
		mergearray(a, first, mid, last, temp); //          
	}
}

bool MergeSort(int a[], int n)
{
	int *p = new int[n];
	if (p == NULL)
		return false;
	mergesort(a, 0, n - 1, p);
	delete[] p;
	return true;
}

の集計ソートの効率は比較的高く、数列の長さをNとし、数列を小数列に分けるにはlognステップが必要であり、各ステップは秩序数列を統合するプロセスである.
時間的複雑度はO(N)と記すことができるので,全部でO(N*logn)となる.集計ソートは毎回隣接するデータで行われるので、
従って、O(N*logn)に集計されるいくつかのソート方法(高速ソート、集計ソート、ヒルソート、スタックソート)も効率的である.
本人のパソコンで泡立ちソート、直接挿入ソート、集計ソートおよび直接使用システムのqsort()を比較する(いずれもReleaseバージョン下)
注意:mergearray()が整列数列をマージするときに一時配列を割り当てる本もありますが、new操作が多すぎると時間がかかります.
だから小さな変化をした.MergeSort()内のnewの一時配列のみです.後の操作では、この一時配列が共有されます.
ヒープのソート
方法1:

//   
void heapSort(int *a, int len)
{
	//     ，         (            )
	int first = (len-2)/2;
	for (int i=first; i>=0; i--)
	{
		adjustHeap(a, len, i);
	}

	int temp;
	for (int j=len-1; j>=0; j--)
	{
		temp = a[j];
		a[j] = a[0];
		a[0] = temp;
		adjustHeap(a, j, 0);//     
	}
}
void adjustHeap (int *array, int len, int i)
{
	int left = 2*i+1;
	int right = 2*i+2;
	int largest = i;
	if (left < len && array[left] > array[i])
		largest = left;
	if (right < len && array[right] > array[largest])
		largest = right;

	int temp;
	if (largest != i)
	{
		temp = array[largest];
		array[largest] = array[i];
		array[i] = temp;
		adjustHeap(array, len, largest);
	}
}

方式2:

#include 
#include 
#include 
using namespace std;
const int HEAP_SIZE = 13; //     

int parent(int);
int left(int);
int right(int);
void Max_Heapify(int [], int, int);
void Build_Max_Heap(int []);
void print(int []);
void HeapSort(int [], int);

/*   */
int parent(int i)
{
	return (int)floor((i - 1) / 2);
}

/*    */
int left(int i)
{
	return (2 * i + 1);
}

/*    */
int right(int i)
{
	return (2 * i + 2);
}

/*            */
void Max_Heapify(int A[], int i, int heap_size)
{
	int l = left(i);
	int r = right(i);
	int largest;
	int temp;
	if(l < heap_size && A[l] > A[i])
	{
		largest = l;
	}
	else
	{
		largest = i;
	}
	if(r < heap_size && A[r] > A[largest])
	{
		largest = r;
	}
	if(largest != i)
	{
		temp = A[i];
		A[i] = A[largest];
		A[largest] = temp;
		Max_Heapify(A, largest, heap_size);
	}
}

/*       */
void Build_Max_Heap(int A[])
{
	for(int i = (HEAP_SIZE-2)/2; i >= 0; i--)
	{
		Max_Heapify(A, i, HEAP_SIZE);
	}
}

/*      */
void print(int A[])
{
	for(int i = 0; i < HEAP_SIZE;i++)
	{
		printf("%d ", A[i]);
	}
	printf("
");
}

/*       */
void HeapSort(int A[], int heap_size)
{
	Build_Max_Heap(A);
	int temp;
	for(int i = heap_size - 1; i >= 0; i--)
	{
		temp = A[0];
		A[0] = A[i];
		A[i] = temp;
		Max_Heapify(A, 0, i);
	}
	print(A);
}

/*          */
int main(int argc, char* argv[])
{
	int A[HEAP_SIZE] = {19, 1, 10, 14, 16, 4, 7, 9, 3, 2, 8, 5, 11};
	HeapSort(A, HEAP_SIZE);
	system("pause");
	return 0;
}