void InsertSort(int* a, int n)
{
	for (int i = 1; i < n; i++)
	{
		int temp = a[i ];
		int j = i;
		for (j = i; j > 0; j--)
		{
			if (a[j - 1] > temp)
			{
				a[j ] = a[j-1];

			}
			else
			{
				break;
			}
		}
		a[j] = temp;
	}
}

void PrintArry(int a[], int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void TestInsertSort()
{
	int arr[] = { 5,2,4,6,1,3 };
	InsertSort(arr, sizeof(arr) / sizeof(arr[0]));
	PrintArry(arr, sizeof(arr) / sizeof(arr[0]));

}
int main()
{
	TestInsertSort();
	return 0;
}

4.直接插入排序总结

<1>待排序的数据越接近有序，直接插入排序的效率越高。

<2>时间复杂度：O(n^2).

<3>空间复杂度：O(1).

<4>稳定性：稳定。

?(2)希尔排序

1.希尔排序算法思想

希尔排序就是将待排序的数据进行分组，然后对每一组进行直接插入排序，达到预排序的效果使得待排序的数据接近有序，然后再次分组，每一个都是使分组间距减小，当分组的间距为一的时候，希尔排序完成。

2.希尔排序思想思想图解

?3.希尔排序的代码及运行结果。

void InsertSort(int* a, int n)
{
	for (int i = 1; i < n; i++)
	{
		int temp = a[i ];
		int j = i;
		for (j = i; j > 0; j--)
		{
			if (a[j - 1] > temp)
			{
				a[j ] = a[j-1];

			}
			else
			{
				break;
			}
		}
		a[j] = temp;
	}
}

void TestShellSort()
{
	int arr[] = { 8,5,2,4,3,6,1,3 };
	ShellSort(arr, sizeof(arr) / sizeof(arr[0]));
	PrintArry(arr, sizeof(arr) / sizeof(arr[0]));

}

?4.希尔排序总结

<1>希尔排序是对直接插入排序的总结

<2>时间复杂度：O(N)~O(N^2)

<3>空间复杂度：O(1);

<4>稳定性：不稳定；

四选择排序

（1）直接选择排序

1.直接选择排序的算法自思想

在待排序的数组中找对找出最大的数据，放在数组的最后面，找到最小的数据放在数组的最后面

以此找次小的和次大的，直到数组有序

2.直接选择排序的思想图解

?3.直接选择排序代码及运行结果

void SelectSort(int* a, int n)
{
	int begin = 0,end = n - 1;
	while (begin < end)
	{
		int mini = begin, maxi = end;
		for (int i = begin; i <= end; i++)
		{

			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		   if (a[i] <a[mini])
			{
				mini = i;
			}
		}
		if (begin == maxi)
			maxi = mini;
		Swap(&a[begin],&a[mini]);
		Swap(&a[end], &a[maxi]);
		begin++;
		end--;

	}
	
}

void TestSelectSort()
{
	int arr[] = { 8,5,2,4,3,6,1,3 };
	SelectSort(arr, sizeof(arr) / sizeof(arr[0]));
	PrintArry(arr, sizeof(arr) / sizeof(arr[0]));

}

?4.直接选择排序总结：

<1>直接选择排序的思想简单，但是效率不好，实际中很少使用

<2>时间复杂度：O（N^2);

<3>空间复杂度O(1)

<4>稳定性：不稳定

（2）堆排序

1.堆排序的思想及图解

?利用堆的特性，就可以堆一组数据进行建堆，从而达到排序的效果。怎样才能使得一组无序的数据在逻辑上呈现堆的结构呢？不难发现，当一个完全二叉树的左子树和右子树都是堆的时候，就可以利用向下渗透的方法将这棵树，变成堆。

这里以小堆为例，当一个完全二叉树的左子树和右子树都是小堆时候。用父亲节点和儿子节点中最小的比较，若儿子节点小于父亲节点，就将儿子节点和父亲节点交换。

向下渗透的过程如图

?有了向下渗透的算法之后，就可以将建小堆采用分治的算法建堆。通过观察，可以发现需要从最后一个非叶子节点开始建堆，而最后一个非叶子节点恰好是最后一个节点的父亲节点。这样就可以使用递归的思想进行建堆。注：想要排升序就建大堆，排降序就建小堆。

以升序为例，建大堆之后将最后一个节点的和第一个节点交换，然后使用向下渗透算法进行调整，直到待排序数据排序完成。

2.堆排序的代码及运行结果。

//向下调整
void AdjustDwon(int* a, int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1;
	while (child < n)
	{
		
		if (child+1<n&&a[child + 1] >a[child])
		{
			child = child + 1;
		}
		if ( a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			
		}
		parent = child;
		child = parent * 2 + 1;

	}
}
void HeapSort(int* a, int n)
{
	//建堆
	int root = (n - 1) / 2;
	while (root>=0)
	{
		AdjustDwon(a, n, root);
		
		root--;
	}
	//排序
	while (n >0)
	{
		Swap(&a[n-1], &a[0]);
		n--;
		AdjustDwon(a, n, 0);
	}
}

void TestHeapSort()
{
	
	int arr[] = { 3,5,2,4,3,6,1,8 };
	HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
	PrintArry(arr, sizeof(arr) / sizeof(arr[0]));
}

3.堆排序总结

<1>.堆排序利用堆的特点来选数，效率就高很多。

<2>时间复杂度：O（N^logN）.

<3>空间复杂度：O(1).

<4>稳定性：不稳定。

四交换排序

（1）冒泡排序

1.冒泡排序的思想

冒泡排序是从第一个数开始向后比较，遇到比这个数大的（小的）进行交换，这样就可以使最大的（最下的）到最后一个位置，多次进行就可以实现排序。

2.冒泡排序思想图解

?3.冒泡排序的代码及运行结果

void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n - i-1; j++)
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
			}
		}
	}
}

void TestBubbleSort()
{
	int arr[] = { 25,6,56,24,9,12,55 };
	BubbleSort(arr, sizeof(arr) / sizeof(arr[0]));
	PrintArry(arr, sizeof(arr) / sizeof(arr[0]));
}

?（2）快速排序

1.快速排序的思想

任取排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都在相应的位置。

2快速排序的思想图解

?3.快速排序的代码及运行结果

快速排序有三种递归的方法

1.挖坑法

挖坑法就是，找待排序数据中的某一个数据作为基准值（一般是第一个或者最后一个），这里以第一个为例，让基准值所在的位置作为坑，从数据的嘴右边开始找，若出现比基准值小的，将找到的这个值填入坑中，找到的值的位置作为新的坑。同时左边找比基准值大的填入坑中，找到的值的位作为行的坑。

?2.左右指针法

左右指针法就是，右边的指针找小于基准值的数据，找到之后于基准值所在的位置交换，这样基准值就来到了右边指针的位置，再从左边开始找第一个大于基准值的数据，基准值所处的位置的数据交换。重复这个过程，直到，左右指针相遇。

?3.前后指针法

前后指针法就是，两个指针一前一后，前后两个指针同时向前走，当第一次遇到大于基准值的数据时，后面的指针停下来，前面的指针继续向前走，当前面的指针遇到比基准值小小的数据时，前面的指针所在的位置的数据于后一个指针所在位置的下一个位置的数据交换，直到，前面的指针将真个待排序数据遍历完。

//三数取中
int GetMInd(int a, int b, int c)
{
	if (a > b)
	{
		if (c > a)
			return a;
		else if (b > c)
			return b;
	}
	else
	{
		if (c > b)
			return b;
		else if (a > c)
			return c;
	}

}
//挖坑法
int QuickSortByPivo(int* a, int left, int right)
{
	int keyi = GetMInd(left, (left + right) / 2, right);
	int pivo = keyi;
	int begin = left;
	int end = right;
	int key = a[keyi];
	while (begin < end)
	{
		if (begin < end && a[end] <= key)
		{
			a[pivo] = a[end];
			pivo = end;
			begin++;
		}
		if (begin < end && a[begin] >= key)
		{
			a[pivo] = a[begin];
			pivo = begin;
			end--;
		}

	}
	a[pivo] = key;
	return pivo;
	
}
//左右指针法
int QuickSortByLR(int* a, int left, int right)
{
	int keyi = GetMInd(left, (left + right) / 2, right);//三数取中
	Swap(&a[keyi], &a[left]);
	int key = a[left];
	while (left < right)
	{
		while (left<right&&a[right] >= key)
		{
			right--;
		}
		Swap(&a[right], &a[left]);
		while (left<right&&a[left] <= key)
		{
			left++;
		}
		Swap(&a[left], &a[right]);
		
	}
	return right;
	
}
//前后指针法
int QuickSortByPC(int* a, int left, int right)
{

	int prev = left - 1;
	int cur = left;
	int key = a[left];
	while (cur <=right)
	{
		if (a[cur] <=key )
		{
			if (cur - prev == 1)
			{
				cur++;
				prev++;
			}
			else
			{
				prev++;
				Swap(&a[cur], &a[prev]);
				cur++;
			}
		}
		else
		{
			cur++;
		}
	}
	Swap(&a[prev], &a[left]);
	return prev;
}


void QuickSort(int* a, int left, int right)
{
	if (left >=right)
		return;
	
	//int pivo = QuickSortByLR(a, left, right);
	//int pivo = QuickSortByPivo(a, left, right);
	int pivo = QuickSortByPC(a, left, right);
	QuickSort(a,left, pivo - 1);
	QuickSort(a,pivo + 1, right);
}

void TestQuickSort()
{
	int arr[]={ 49, 38, 65, 97, 76, 13, 27, 49 };
	QuickSort(arr, 0, sizeof(arr) / sizeof(arr[0]) -1);
	PrintArry(arr, sizeof(arr) / sizeof(arr[0]));

}

4.快速排序总结

<1>快速排序的整体应用场景比较好。

<2>时间复杂度：O(N*logN)。

<3>空间复杂度：O(1)。

<4>稳定性：不稳定。

五归并排序

1 归并排序

1.归并排序的思想

归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

2.归并排序的思想图解

?3.归并排序代码及运行结果

void _MergeSort(int* a,int*temp, int left, int right)
{
	int mind = (left + right) / 2;
	int begin1 = left, end1 = mind;
	int begin2 = mind + 1, end2 = right;
	if (left >= right)
	{
		return;
	}
	_MergeSort(a, temp, begin1, end1);
	_MergeSort(a, temp, begin2, end2);
	
		int index = left;
		while (begin1 <= end1 && begin2 <= end2)
		{
			if (a[begin1] < a[begin2])
			{
				temp[index++] = a[begin1++];
			}
			else
			{
				temp[index++] = a[begin2++];
			}
		}
		while (begin1 <= end1)
		{
			temp[index++] = a[begin1++];
		}
		while (begin2 <= end2)
		{
			temp[index++] = a[begin2++];
		}
		for (int i = left; i <= right; ++i)
		{
			a[i] = temp[i];
		}

}

void MergeSort(int* a, int n)
{
	int right = n - 1;
	int left = 0;
	int* temp =(int*) malloc(sizeof(int) * n);
	assert(temp);
	_MergeSort(a, temp, 0, n - 1);
	free(temp);
}

void TestMergeSort()
{
	int arr[] = { 10,6,7,1,3,9 ,4,2};
	MergeSort(arr, sizeof(arr) / sizeof(arr[0]));
	PrintArry(arr, sizeof(arr) / sizeof(arr[0]));
}

4.归并排序总结

1. 归并的缺点在于需要 O(N) 的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问

题。

2. 时间复杂度： O(N*logN)

3. 空间复杂度： O(N)

4. 稳定性：稳定

六各排序算法性能测试

void TestOP()
{
	int N = 100000;
	srand((unsigned)time(NULL));
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) *N);
	int* a3 = (int*)malloc(sizeof(int) * N);
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);
	int* a6 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
		a3[i] = a1[i];
		a4[i] = a1[i];
		a5[i] = a1[i];
		a6[i] = a1[i];
	}
	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();
	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();
	int begin3 = clock();
	SelectSort(a3, N);
	int end3 = clock();
	int begin4 = clock();
	HeapSort(a4, N);
	int end4 = clock();
	int begin5 = clock();
	QuickSort(a5, 0, N - 1);
	int end5 = clock();
	int begin6 = clock();
	MergeSort(a6, N);
	int end6 = clock();
	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	printf("SelectSort:%d\n", end3 - begin3);
	printf("HeapSort:%d\n", end4 - begin4);
	printf("QuickSort:%d\n", end5 - begin5);
	printf("MergeSort:%d\n", end6 - begin6);
	free(a1);
	free(a2);
	free(a3);
	free(a4);
	free(a5);
	free(a6);
}