排序算法（一）

排序算法可以分为内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记录，在排序过程中需要访问外存。常见的内部排序算法有：插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括：

总体概述：

一、 冒泡排序

1、 算法步骤

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

2、 图片演示

3、 代码演示

#include<stdio.h>

void bubble(int* arr, int len) 
{
	for (size_t i = 0; i < len - 1; i++)
	{
		for (size_t j = 0; j < len - i - 1; j++)
		{
			if (arr[j] > arr[j + 1])  // 升序排序，如果要为降序排序，则换成小于号
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

int main()
{
	int arr[] = {1, 3, 7, 6, 2};
	bubble(arr, 5);
	for (size_t i = 0; i < 5; i++)
	{
		printf_s("%d\t", *(arr + i));
	}
    return 0;
}

二、 选择排序

1、 算法步骤

• 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置
• 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾
• 重复第二步，直到所有元素均排序完毕

2、 图片展示

3、 代码实现

#include <stdio.h>

void selection(int* arr, int len)
{ 
	for (size_t i = 0; i < len - 1; i++)
	{
		for (size_t j = i + 1; j < len; j++)
		{
			if (arr[i] > arr[j])  // 升序排序
			{ 
				int temp = arr[i];
				arr[i] = arr[j];-
				arr[j] = temp; 
			}
		}
	}
}

int main()
{
	int arr[] = {1, 3, 7, 6, 2};
	selection(arr, 5);
	for (size_t i = 0; i < 5; i++)
	{
		printf_s("%d\t", *(arr + i));
	}
    return 0;
}

三、 插入排序

1、 算法步骤

• 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
• 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

2、 图片展示

3、 代码实现

#include <stdio.h>

void insertion(int* arr, int len)
{
    int j;
	for (int i = 1; i < len; i++)
	{
		int key = arr[i];  // 注意，这里要使用key来存储索引为i处的值，使其可以与里面排好序的数组进行对比，因为在插入排序中arr[i]的值会改变，这使得需要创建一个变量存储原来的数值
		for (j = i - 1; j >= 0 && arr[j] > key; j--)
		{
			arr[j + 1] = arr[j];  // 把符合条件的值，覆盖到原来的位置
		}
        arr[j + 1] = key;  // 在判断完后，将原来的值赋值给新的位置上
	}
}
int main()
{
	int arr[] = {1, 3, 7, 6, 2};
	insertion(arr, 5);
	for (size_t i = 0; i < 5; i++)
	{
		printf_s("%d\t", *(arr + i));
	}
    return 0;
}

四、 希尔排序

1、 算法步骤

• 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1
• 按增量序列个数 k，对序列进行 k 趟排序
• 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度

2、 图片演示

3、 代码实现

#include <stdio.h>


void shell(int* arr, int len)
{
	int j;
	for (int gap = len  /  2; gap > 0; gap /= 2)  // 这个gap的取值可以自己定义，但是要动态变化的
	{
		for (int i = gap; i < len; i++) 
		{
			// 进行插入排序
			int temp = arr[i];
			for (j = i - gap; j >= 0 && arr[j] > temp; j -= gap)
			{
				arr[j + gap] = arr[j];  // 如果符合条件，不断的
			}
			arr[j + gap] = temp;  // 交换最终位置
		}
	}
}
int main()
{
	int arr[] = {1, 3, 7, 6, 2};
	shell(arr, 5);
	for (size_t i = 0; i < 5; i++)
	{
		printf_s("%d\t", *(arr + i));
	}
    return 0;
}

五、 归并排序

1、 算法步骤

• 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
• 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
• 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
• 重复步骤 3 直到某一指针达到序列尾；
• 将另一序列剩下的所有元素直接复制到合并序列尾。

2、 图片演示

3、 代码实现

#include <stdio.h>
#include <stdlib.h>



void merge_sort(int arr[], int len) {
    int* a = arr;  // 使用指针接收数组
    int* b = (int*)malloc(len * sizeof(int));  // 申请内存空间
    int seg, start;  // 定义索引
    for (seg = 1; seg < len; seg += seg) 
    {
        for (start = 0; start < len; start += seg * 2) 
        {
            int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];  // 对分割的两个数组进行排序，同时存入临时数组
            // 将多余的数存入数组，因为其为有序的，直接存入最后即可
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int* temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) 
    {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}


int main() {
    int arr[] = { 1, 3, 7, 6, 2 };
    merge_sort(arr, 5);
    for (size_t i = 0; i < 5; i++)
    {
        printf_s("%d\t", *(arr + i));
    }
	return 0;
}

原文地址：http://www.cnblogs.com/liuzhongkun/p/16819749.html