排序 Sort

排序 Sort

算法复杂度

冒泡排序 Bubble

相邻比较+换位

void BubbleSort(int *arr, int len)  
{  
    int i, j, tmp;  
    for (i = 0; i < len - 1; i++) {  
        for (j = 0; j < len - i - 1; j++) {  
            if (arr[j] > arr[j+1]) {  
                tmp = arr[j];  
                arr[j] = arr[j+1];  
                arr[j+1] = tmp;  
            }  
        }  
    }  
}  
``` 
![冒泡](algorithm-sort/BubbleSort.gif)
## 选择排序 Select
向后查找最小元, 与每一轮首位换位
```c 
void SelectionSort(int *arr, int len)
{
    int i, j, min, tmp;
    for (i = 0; i < len - 1; i++) {
        min = i;
        for (j = i + 1; j < len; j++) {
            if (arr[j] < arr[min]) {
                min = j;// 修改最小元
            }
        }
        tmp = arr[min];
        arr[min] = arr[i];
        arr[i] = tmp;
    }
}
Copy

插入排序 Insert

从第二个开始抽出来, 和前面的比较并排位

void InsertionSort(int *arr, int len)    
{    
    int i, j, tmp;    
    for (i = 1; i < len; i++) { 
        //从第二个开始   
        if (arr[i] < arr[i-1]) {   // 如果小于前一个 
            tmp = arr[i];          // 要移动的元放到temp中
            for (j = i - 1; j >= 0 && arr[j] > tmp; j--) {  
                //向前顺位
                arr[j+1] = arr[j];    
            }  
            arr[j+1] = tmp;    
        }          
    }    
}
Copy

希尔排序 Shell

按增量分批做插入排序

// 希尔排序
void ShellSort(int *arr, int size)  
{  
    int i, j, tmp, increment;  
    for (increment = size/ 2; increment > 0; increment /= 2) {    
        for (i = increment; i < size; i++) {  
            // 做插入排序
            tmp = arr[i];  
            for (j = i - increment; j >= 0 && tmp < arr[j]; j -= increment) {  
                arr[j + increment] = arr[j];  
            }  
            arr[j + increment] = tmp;
        }  
    }  
}
Copy

归并排序 Merge

分治法

void merge(int arr[], int low, int mid, int high){
    int i, k;
    int *tmp = (int *)malloc((high-low+1)*sizeof(int));
    //申请空间，使其大小为两个
    int left_low = low;
    int left_high = mid;
    int right_low = mid + 1;
    int right_high = high;
    for(k=0; left_low<=left_high && right_low<=right_high; k++){  // 比较两个指针所指向的元素
        if(arr[left_low]<=arr[right_low]){
            tmp[k] = arr[left_low++];
        }else{
            tmp[k] = arr[right_low++];
        }
    }
    if(left_low <= left_high){  //若第一个序列有剩余，直接复制出来粘到合并序列尾
        //memcpy(tmp+k, arr+left_low, (left_high-left_low+l)*sizeof(int));
        for(i=left_low;i<=left_high;i++)
            tmp[k++] = arr[i];
    }
    if(right_low <= right_high){ //若第二个序列有剩余，直接复制出来粘到合并序列尾
        //memcpy(tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int));
        for(i=right_low; i<=right_high; i++)
            tmp[k++] = arr[i];
    }
    // 从tmp复制回arr内
    for(i=0; i<high-low+1; i++)
        arr[low+i] = tmp[i];
    free(tmp);
    return;
}
void MergeSort(int arr[], unsigned int first, unsigned int last){
    int mid = 0;
    if(first<last){
        mid = (first+last)/2; /* 注意防止溢出 */
        /*mid = first/2 + last/2;*/
        //mid = (first & last) + ((first ^ last) >> 1);
        MergeSort(arr, first, mid);
        MergeSort(arr, mid+1,last);
        merge(arr,first,mid,last);
    }
    return;
}
Copy

快速排序 Quick

分块排序, 且左块皆小于右块

形式 1 （对应动图）

void swap(int *a, int *b){  
    int temp;  
    temp = *a;  
    *a = *b;  
    *b = temp;  
}  
void QuickSort(int *arr, int maxlen, int begin, int end){  
void QuickSort(int *arr, int maxlen, int begin, int end)
{
    printf("\nQuickSort(%d->%d)\n", begin, end);
    int i, store;
    if (begin - end >= -1){
        return;
    }
    // arr[begin]为轴心点（与他比较）（亮黄色）
    i = begin + 1;     // 试探（红色）
    store = begin + 1; // 存储指数（紫色最左）
    while (i < end){
        if (arr[i] < arr[begin]){
            swap(&arr[i], &arr[store]); // 移动过去的都是比轴心点小的
            store++; // 指向的是不满足判断条件的那个点（比轴心点大）
        }
        i++;
    }
    swap(&arr[store - 1], &arr[begin]); // 轴心点数值跳到那些都比他小的最右
    printf("\n");
    QuickSort(arr, maxlen, begin, store - 1);
    QuickSort(arr, maxlen, store, end);
}
Copy

形式 2

void QuickSort(int *arr, int maxlen, int begin, int end){  
    int i, j;  
    if (begin < end) {  
        // arr[begin]为轴心点（与他比较）
        i = begin + 1;  
        j = end;
        while (i < j) {  
            if(arr[i] > arr[begin]) {  
                swap(&arr[i], &arr[j]);
                j--;  
            } else {  
                i++;        // 否则继续往后看
            }  
        }                   // 循环跳出后i,j一样
        if (arr[i] >= arr[begin]) {  
            i--;  
        }  
        swap(&arr[begin], &arr[i]);
        QuickSort(arr, maxlen, begin, i);  
        QuickSort(arr, maxlen, j, end);  
    }  
}
Copy

堆排序 Heap

#define LeftChild(i) (2*(i)+1)
void PercDown(int A[],int i, int N){                  // 下滤
    int Child;
    int Tmp;
    for (Tmp=A[i];LeftChild(i)<N;i=Child){            // Tmp为第一个本体的值 , 每次更新i为指向的子节点(较大者)
        Child = LeftChild(i);                         // 指向左子节点
        if(Child != N-1 && A[Child + 1] > A[Child]){  // 子节点不在最末(不然会爆) 且 右子节点>左子节点
            Child++;                                  // 从左子节点指向右子节点
        }
        if(Tmp < A[Child]){                           // 如果本体小于子节点最大的那个,
            A[i] = A[Child];                          // 把子节点覆盖到本体.
        }else{
            break;                                    // 一旦本体已经最大则跳出
        }
    }
    A[i] = Tmp;                                       // 把元初本体的值放到最后指向的子节点
}
void HeapSort(int A[],int N){
    int i;
    for (i=N/2;i>=0;i--){                             // 从倒数第二层向上过滤排序
        PercDown(A,i,N);                              // 构造大顶堆
    }
    for (i = N-1;i>0;i--){
        swap(&A[0],&A[i]);                            // 每换一次位(提取最大值到最后),
        PercDown(A,0,i);                              // 又要再做一次下滤.
    }
}
Copy

基数排序

// TODO: 略
Copy

计数排序

// TODO: 略
Copy

桶排序

// TODO: 略
Copy

随机快速排序

// TODO: 略
Copy

1	void BubbleSort(int *arr, int len)
2	{
3	int i, j, tmp;
4	for (i = 0; i < len - 1; i++) {
5	for (j = 0; j < len - i - 1; j++) {
6	if (arr[j] > arr[j+1]) {
7	tmp = arr[j];
8	arr[j] = arr[j+1];
9	arr[j+1] = tmp;
10	}
11	}
12	}
13	}
14	```
15	![冒泡](algorithm-sort/BubbleSort.gif)
16
17	## 选择排序 Select
18	向后查找最小元, 与每一轮首位换位
19	```c
20	void SelectionSort(int *arr, int len)
21	{
22	int i, j, min, tmp;
23	for (i = 0; i < len - 1; i++) {
24	min = i;
25	for (j = i + 1; j < len; j++) {
26	if (arr[j] < arr[min]) {
27	min = j;// 修改最小元
28	}
29	}
30	tmp = arr[min];
31	arr[min] = arr[i];
32	arr[i] = tmp;
33	}
34	}

1	void merge(int arr[], int low, int mid, int high){
2	int i, k;
3	int tmp = (int )malloc((high-low+1)*sizeof(int));
4	//申请空间，使其大小为两个
5	int left_low = low;
6	int left_high = mid;
7	int right_low = mid + 1;
8	int right_high = high;
9
10	for(k=0; left_low<=left_high && right_low<=right_high; k++){ // 比较两个指针所指向的元素
11	if(arr[left_low]<=arr[right_low]){
12	tmp[k] = arr[left_low++];
13	}else{
14	tmp[k] = arr[right_low++];
15	}
16	}
17
18	if(left_low <= left_high){ //若第一个序列有剩余，直接复制出来粘到合并序列尾
19	//memcpy(tmp+k, arr+left_low, (left_high-left_low+l)*sizeof(int));
20	for(i=left_low;i<=left_high;i++)
21	tmp[k++] = arr[i];
22	}
23
24	if(right_low <= right_high){ //若第二个序列有剩余，直接复制出来粘到合并序列尾
25	//memcpy(tmp+k, arr+right_low, (right_high-right_low+1)*sizeof(int));
26	for(i=right_low; i<=right_high; i++)
27	tmp[k++] = arr[i];
28	}
29
30	// 从tmp复制回arr内
31	for(i=0; i<high-low+1; i++)
32	arr[low+i] = tmp[i];
33	free(tmp);
34	return;
35	}
36
37	void MergeSort(int arr[], unsigned int first, unsigned int last){
38	int mid = 0;
39	if(first<last){
40	mid = (first+last)/2; /* 注意防止溢出 */
41	/mid = first/2 + last/2;/
42	//mid = (first & last) + ((first ^ last) >> 1);
43	MergeSort(arr, first, mid);
44	MergeSort(arr, mid+1,last);
45	merge(arr,first,mid,last);
46	}
47	return;
48	}

1	#define LeftChild(i) (2*(i)+1)
2
3	void PercDown(int A[],int i, int N){ // 下滤
4	int Child;
5	int Tmp;
6	for (Tmp=A[i];LeftChild(i)<N;i=Child){ // Tmp为第一个本体的值 , 每次更新i为指向的子节点(较大者)
7	Child = LeftChild(i); // 指向左子节点
8	if(Child != N-1 && A[Child + 1] > A[Child]){ // 子节点不在最末(不然会爆) 且右子节点>左子节点
9	Child++; // 从左子节点指向右子节点
10	}
11	if(Tmp < A[Child]){ // 如果本体小于子节点最大的那个,
12	A[i] = A[Child]; // 把子节点覆盖到本体.
13	}else{
14	break; // 一旦本体已经最大则跳出
15	}
16	}
17	A[i] = Tmp; // 把元初本体的值放到最后指向的子节点
18	}
19
20	void HeapSort(int A[],int N){
21	int i;
22	for (i=N/2;i>=0;i--){ // 从倒数第二层向上过滤排序
23	PercDown(A,i,N); // 构造大顶堆
24	}
25	for (i = N-1;i>0;i--){
26	swap(&A[0],&A[i]); // 每换一次位(提取最大值到最后),
27	PercDown(A,0,i); // 又要再做一次下滤.
28	}
29	}

1	void InsertionSort(int *arr, int len)
2	{
3	int i, j, tmp;
4	for (i = 1; i < len; i++) {
5	//从第二个开始
6	if (arr[i] < arr[i-1]) { // 如果小于前一个
7	tmp = arr[i]; // 要移动的元放到temp中
8	for (j = i - 1; j >= 0 && arr[j] > tmp; j--) {
9	//向前顺位
10	arr[j+1] = arr[j];
11	}
12	arr[j+1] = tmp;
13	}
14	}
15	}

1	// 希尔排序
2	void ShellSort(int *arr, int size)
3	{
4	int i, j, tmp, increment;
5	for (increment = size/ 2; increment > 0; increment /= 2) {
6	for (i = increment; i < size; i++) {
7	// 做插入排序
8	tmp = arr[i];
9	for (j = i - increment; j >= 0 && tmp < arr[j]; j -= increment) {
10	arr[j + increment] = arr[j];
11	}
12	arr[j + increment] = tmp;
13	}
14	}
15	}

1	void swap(int a, int b){
2	int temp;
3	temp = *a;
4	a = b;
5	*b = temp;
6	}
7	void QuickSort(int *arr, int maxlen, int begin, int end){
8	void QuickSort(int *arr, int maxlen, int begin, int end)
9	{
10	printf("\nQuickSort(%d->%d)\n", begin, end);
11	int i, store;
12	if (begin - end >= -1){
13	return;
14	}
15	// arr[begin]为轴心点（与他比较）（亮黄色）
16	i = begin + 1; // 试探（红色）
17	store = begin + 1; // 存储指数（紫色最左）
18	while (i < end){
19	if (arr[i] < arr[begin]){
20	swap(&arr[i], &arr[store]); // 移动过去的都是比轴心点小的
21	store++; // 指向的是不满足判断条件的那个点（比轴心点大）
22	}
23	i++;
24	}
25
26	swap(&arr[store - 1], &arr[begin]); // 轴心点数值跳到那些都比他小的最右
27	printf("\n");
28	QuickSort(arr, maxlen, begin, store - 1);
29	QuickSort(arr, maxlen, store, end);
30	}

1	void QuickSort(int *arr, int maxlen, int begin, int end){
2	int i, j;
3	if (begin < end) {
4	// arr[begin]为轴心点（与他比较）
5	i = begin + 1;
6	j = end;
7	while (i < j) {
8	if(arr[i] > arr[begin]) {
9	swap(&arr[i], &arr[j]);
10	j--;
11	} else {
12	i++; // 否则继续往后看
13	}
14	} // 循环跳出后i,j一样
15	if (arr[i] >= arr[begin]) {
16	i--;
17	}
18	swap(&arr[begin], &arr[i]);
19	QuickSort(arr, maxlen, begin, i);
20	QuickSort(arr, maxlen, j, end);
21	}
22	}