排序方法总结

#ifndef MYSORT_H_INCLUDED
#define MYSORT_H_INCLUDED

/*
交换排序：冒泡排序，快速排序
*/
void bubbleSort(int arr[], int arrLen);
int slipForQuickSort(int arr[], int arrLeft, int arrRight);
void quickSort(int arr[], int arrLeft, int arrRight);

/*
选择排序：直接选择排序，堆排序
*/
void directSelectSort(int arr[], int arrLen);
void heapAdjust(int arr[], int parent, int arrLen);
void heapSort(int arr[], int arrLen);

/*
插入排序：直接插入排序，希尔排序
*/
void directInsertSort(int arr[], int arrLen);
void shellSort(int arr[], int arrLen);

/*
合并排序：归并排序
*/
void mergeSort(int arr[], int temparr[], int left, int right);
void merge(int array[], int temparray[], int left, int middle, int right);
#endif // MYSORT_H_INCLUDED

#include "mysort.h"
#include "stdio.h"

void playArr(int arr[], int len)
{
	int i = 0;
	for (i = 0; i < len - 1; i++)
	{
	    printf("%d\t", arr[i]);
	}
    printf("\n");
	return;
}

void swapNum(int *a, int *b)
{
	int tmp;
	tmp = *a;
	*a = *b;
	*b = tmp;
	return;
}
/*
冒泡排序是交换排序，O(N^2)
*/
void bubbleSort(int arr[], int arrLen)
{
	int i;
	int j;

	for (i = 0; i < arrLen; i++)
	{
		for (j = arrLen - 1; j > i; j--)
		{
			if (arr[j] < arr[i])
			{
				swapNum(&arr[i], &arr[j]);
			}
		}
	}
	return;
}

/*
快速排序是交换排序，O(N^2),平均复杂度：N(logN)
int arrLeft, int arrRight 是数组下标
*/
void quickSort(int arr[], int arrLeft, int arrRight)
{
	int i;

	if (arrLeft < arrRight)
	{
		i = slipForQuickSort(arr, arrLeft, arrRight);

		quickSort(arr, arrLeft, i - 1);
		quickSort(arr, i + 1, arrRight);
	}
	return;
}

int slipForQuickSort(int arr[], int arrLeft, int arrRight)
{
	int baseNum = arr[arrLeft];

	while (arrLeft < arrRight)
	{
		//从右到左查询比baseNum小的数字
		while ((arrLeft < arrRight) && (arr[arrRight] >= baseNum))
		{
			arrRight--;
		}
		arr[arrLeft] = arr[arrRight];	//在右边找到之后将比baseNum小的数字移动到数组的左边

		//从左到右查询比baseNum大的数字
		while ((arrLeft < arrRight) && (arr[arrLeft] <= baseNum))
		{
			arrLeft++;
		}
		arr[arrRight] = arr[arrLeft];	//在左边找到之后将比baseNum大的数字移动到数组的右边
	}

	arr[arrLeft] = baseNum;		//把基准数字放到arrLeft位置上，此时arrLeft左边都是比baseNum小的数字，右边都是比它大的数字

	return arrLeft;
}

/*
直接插入排序：O(n^2)
*/
void directSelectSort(int arr[], int arrLen)
{
	int i;
	int j;
	int baseNum;

	for (i = 0; i < arrLen; i++)
	{
		baseNum = i;

		//在i的右侧找到最下的一个数字，记录下标
		for (j = i + 1; j < arrLen; j++)
		{
			if (arr[j] < arr[baseNum])
			{
				baseNum = j;
			}
		}

		//将最小的数字移动到当前位置
		swapNum(&arr[i], &arr[baseNum]);
	}

	return;
}

/*
堆排序：O(NlogN)
*/
void heapSort(int arr[], int arrLen)
{
	int i;

	//二叉树父节点的下标为i时，左右孩子接到为2i+1，2i+2。
	for (i = arrLen / 2 - 1; i >= 0; i--)
	{
		heapAdjust(arr, i, arrLen);
	}

	for (i = arrLen - 1; i >= 0  /*arrLen - top */; i--)
	{
		swapNum(&arr[0], &arr[i]);	//将大数放到数组最右边
		heapAdjust(arr, 0, i - 1);	//将剩余的数字从新构建大根堆
	}

	return;
}

void heapAdjust(int arr[], int parent, int arrLen)
{
	int tmp;
	int leftChild;

	tmp = arr[parent];          //取出父节点的值并保持
	leftChild = 2 * parent + 1;     //找到父节点的左孩子

	while (leftChild < arrLen)
	{
		if ((leftChild + 1 < arrLen) && (arr[leftChild] < arr[leftChild +1]))
		{
			leftChild++;
		}

		if (tmp >= arr[leftChild])
		{
			break;
		}

		arr[parent] = arr[leftChild];
		parent = leftChild;
		leftChild = 2 * parent + 1;
	}

	arr[parent] = tmp;
	return;
}

/*
直接插入排序：O(N^2) 将N-M个无序数字，插入前面M个有序数字中
*/
void directInsertSort(int arr[], int arrLen)
{
	int i;
	int j;
	int tmp;

	for (i = 1; i < arrLen; i++)
	{
		tmp = arr[i];

		for (j = i - 1; ((j >= 0) && (arr[j] > tmp)); j--)
		{
			arr[j + 1] = arr[j];
		}

		arr[j + 1] = tmp;
	}
}

/*
希尔排序：平均为：O(N^3/2) 最坏： O(N^2)
*/
void shellSort(int arr[], int arrLen)
{
	int i;
	int j;
	int tmp;
	int addNum;

	addNum = arrLen / 2;	//增量
	while (addNum >= 1)
	{
		for (i = addNum; i < arrLen; i++)
		{
			tmp = arr[i];
			for (j = i - addNum; ((j >= 0) && (tmp < arr[j])); j = j - addNum)
			{
				arr[j + addNum] = arr[j];
			}
			arr[j + addNum] = tmp;
		}
		addNum /= 2;
	}

	return;
}

/*
归并排序： 时间：O(NlogN) 空间：O(N)
int left, int right 为数组下标
*/
void mergeSort(int arr[], int temparr[], int left, int right)
{
    int middle;

    if (left < right)
    {
        middle = (left + right) / 2;    //拆分位置

        mergeSort(arr, temparr, left, middle);
        mergeSort(arr, temparr, middle + 1, right);

        merge(arr, temparr, left, middle + 1, right);
    }
    return;
}

void merge(int array[], int temparray[], int left, int middle, int right)
{
    int i;
    //左指针尾
    int leftEnd = middle - 1;
    //右指针头
    int rightStart = middle;

    //临时数组的下标
    int tempIndex = left;

    //数组合并后的length长度
    int tempLength = right - left + 1;

    //先循环两个区间段都没有结束的情况
    while ((left <= leftEnd) && (rightStart <= right))
    {
        //如果发现有序列大，则将此数放入临时数组
        if (array[left] < array[rightStart])
            temparray[tempIndex++] = array[left++];
        else
            temparray[tempIndex++] = array[rightStart++];
    }

     //判断左序列是否结束
     while (left <= leftEnd)
         temparray[tempIndex++] = array[left++];

     //判断右序列是否结束
     while (rightStart <= right)
         temparray[tempIndex++] = array[rightStart++];

     //交换数据
     for (i = 0; i < tempLength; i++)
     {
         array[right] = temparray[right];
         right--;
     }

     return;
}