* 好久都没看排序算法了。。。今天把以前的代码贴上来。。。方便今后随时复习→_→ *

1. 交换排序

   void swap_sort(int *arr, int len)
   {
   	for (int i = 0; i < len - 1; ++i)//最后一个不用再向后比较
   	{
   		for (int j = i + 1; j < len; ++j)
   		{
   			if (arr[i] > arr[j])//不相邻交换，较大值向后移动，较小值向前移动
   			{
   				int tmp = arr[i];
   				arr[i] = arr[j];
   				arr[j] = tmp;
   			}
   		}
   	}
   }

2. 冒泡排序

   void bubble_sort(int *arr, int len)
   {
   	bool flag = true;
   	for (int i = 0; i < len - 1 && flag; ++i)//最后一个不用再向后比较
   	{
   		flag = false;
   		for (int j = 0; j < len - 1 - i; ++j)//排除最后已经排序好的
   		{
   			if (arr[j] > arr[j + 1])//相邻交换
   			{
   				flag = true;
   				int tmp = arr[j];
   				arr[j] = arr[j + 1];
   				arr[j + 1] = tmp;
   			}
   		}
   	}
   }

3. 选择排序

   void select_sort(int *arr, int len)
   {
   	int min = arr[0];
   	int min_index = 0;
   	int i = 0;
   	int j = 0;
   	for (i = 0; i < len - 1; ++i)
   	{
   		min = arr[i];
   		min_index = i;
   		for (j = i + 1; j < len; ++j)//一次循环找出最小数的数值和下标且和arr[i]交换
   		{
   			if (min > arr[j])
   			{
   				min = arr[j];
   				min_index = j;
   			}
   		}
   		if (i != min_index)
   		{
   			int tmp = arr[i];
   			arr[i] = arr[min_index];
   			arr[min_index] = tmp;
   		}
   	}
   }

4. 插入排序

   void insert_sort(int *arr, int len)
   {
   	int j = 0;
   	int tmp = 0;
   	for (int i = 1; i < len; ++i)
   	{
   		tmp = arr[i];
   		for (j = i - 1; j >= 0; --j)//arr[i]从arr[i-1]开始逆向比较
   		{
   			if (arr[j] < tmp)//遇到比自己小的为止
   			{
   				break;
   			}
   			arr[j + 1] = arr[j];//比自己大的值后移
   		}
   		arr[j + 1] = tmp;//插入合适位置
   	}
   }

5. 希尔排序

   static void shell(int *arr, int len, int gap)//insert_sort()的变形，insert_sort()一数一组
   {
   	int j = 0;
   	int tmp = 0;
   	for (int i = gap; i < len; ++i)//gap个为一组
   	{
   		tmp = arr[i];
   		for (j = i - gap; j >= 0; j-=gap)
   		{
   			if (arr[j] < tmp)
   			{
   				break;
   			}
   			arr[j + gap] = arr[j];
   		}
   		arr[j + gap] = tmp;
   	}
   }
   
   void shell_sort(int *arr, int len)
   {
   	shell(arr, len, 3);//多次分组。提高效率，使得数逐渐基本有序
   	shell(arr, len, 1);
   }

6. 快速排序

   static int partition(int *arr ,int left, int right)
   {
   	int tmp = arr[left];
   	while (left < right)//直到left和right重合，此时合适位置找到
   	{
   		while (arr[right] > tmp && left < right)
   		{
   			right--;
   		}
   		arr[left] = arr[right];
   
   		while (arr[left] < tmp && left < right)
   		{
   			left++;
   		}
   		arr[right] = arr[left];
   	}
   	arr[left] = tmp;//合适位置赋值
   	return left;
   }
   
   static void quick(int *arr, int left, int right)
   {
   	if (left < right)
   	{
   		//将arr[left]放到合适位置，将枢轴返回出来,pivot左侧的都小于arr[left],右侧的都大于
   		int pivot = partition(arr, left, right);
   		quick(arr, left, pivot - 1);//枢轴两侧开始递归
   		quick(arr, pivot + 1, right);
   	}
   }
   
   void quick_sort(int *arr, int len)//递归快速排序
   {
   	quick(arr, 0, len - 1);
   }
   
   void quick_sort_loop(int *arr, int len)//非递归快速排序
   {
   	DSEQ_STACK *stack = init_seqstack();
   	assert(stack != NULL);
   
   	int left = 0;
   	int right = len - 1;
   	int pivot = 0;
   
   	push(stack, &left);
   	push(stack, &right);
   
   	while (!is_empty(stack))//模拟递归，栈为空时，递归结束
   	{
   		pop(stack, &right);
   		pop(stack, &left);
   		pivot = partition(arr, left, right);//返回第一次的枢轴
   		if (left < pivot - 1)//左侧还有数
   		{
   			int base = pivot - 1;
   			push(stack, &left);
   			push(stack, &base);
   		}
   		if (right > pivot + 1)//右侧还有数
   		{
   			int base = pivot + 1;
   			push(stack, &base);
   			push(stack, &right);
   		}
   	}
   	destory_seqstack(stack);
   }

7. 堆排序

   static void hell(int *arr, int len)//初始排序为大根堆
   {
   	for (int start = len / 2 - 1; start >= 0; start--)//每个大根堆的根
   	{
   		int tmp = arr[start];
   		int i = 0;
   		for (i = 2 * start + 1; i < len; i = 2 * i + 1)//其根与其孩子的关系
   		{
   			if (i + 1 < len&&arr[i] < arr[i + 1])//判断是否有右孩子，若有i停在数值大的孩子上
   			{
   				i++;
   			}
   			if (arr[i] < tmp)//孩子都小于tmp
   			{
   				break;
   			}
   			else if (arr[i] > tmp)//大的数值换到根上
   			{
   				arr[start] = arr[i];
   			}
   			else
   			{
   				;
   			}
   			start = i;//start移动到i处
   		}
   		arr[start] = tmp;//循环结束将tmp放到合适的根上
   	}
   }
   
   static void hell_adjust(int *arr, int len)
   {
   	hell(arr, len);
   }
   
   void hell_sort(int *arr, int len)
   {
   	int tmp = 0;
   	hell(arr, len);
   	for (int i = len-1; i>0; --i)//最大值下放到arr[i]
   	{
   		tmp = arr[i];
   		arr[i] = arr[0];
   		arr[0] = tmp;
   		hell_adjust(arr, i-1);//调整大根堆
   	}
   }

8. 归并排序

   static void meger(int *arr, int len, int gap)
   {
   	int *buff = (int *)malloc(sizeof(int)*len);//开辟存放分组后的成员序列
   	assert(buff != NULL);
   
   	int k = 0;
   	int low1 = 0;
   	int high1 = low1 + gap - 1;
   	int low2 = high1 + 1;
   	int high2 = low2 + gap - 1 < len ? low2 + gap - 1 : len - 1;//防止归并段2第一次就越界
   
   	while (low2 < len)//归并段2有数据时
   	{
   		while (low1 <= high1 && low2 <= high2)//谁小谁下
   		{
   			if (arr[low1] <= arr[low2])
   			{
   				buff[k++] = arr[low1++];
   			}
   			else if (arr[low1] > arr[low2])
   			{
   				buff[k++] = arr[low2++];
   			}
   		}
   		while (low1 <= high1)//未完的补齐
   		{
   			buff[k++] = arr[low1++];
   		}
   		while (low2 <= high2)
   		{
   			buff[k++] = arr[low2++];
   		}
   		low1 = high2 + 1;
   		high1 = low1 + gap - 1;
   		low2 = high1 + 1;
   		high2 = low2 + gap - 1 < len ? low2 + gap - 1 : len - 1;//归并段2中有数据时，防止越界
   	}
   	while (low1 < len)//只有归并段1中有数据
   	{
   		buff[k++] = arr[low1++];
   	}
   	for (int i = 0; i < len; ++i)//复制到buff中
   	{
   		arr[i] = buff[i];
   	}
   	free(buff);
   }
   
   void meger_sort(int *arr, int len)
   {
   	for (int gap = 1; gap < len; gap *= 2)//22--44--88--...分组
   	{
   		meger(arr, len, gap);
   	}
   }