排序方法總結

mySort.h

#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

mySort.c

#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;
}