左程云视频算法笔记03 选择排序

题目二
选择排序
比如一个数组有10个数字，它们的下标 是 0 到 10-1,在3下标位置处有个数字为2，它与0下标位置处的数字对比，如果小于，则放到0下标位置处，然后减减，接着在4下标位置处有个数字5，它与1下标位置处对比，如果小于，调换位置，在减减

#include <iostream>
using namespace std;
void Swap(int arr[], int i, int j)
{
	int temp = arr[j];
	 arr[j] = arr[i];
	 arr[i] = temp;
}

void printarr(int arr[],int x)
{

	for (int i = 0; i < x; ++i)
	{
		cout << arr[i] <<" ";
	}
	cout << endl;
}


void selectSort(int arr[],int x)
{
	int N = x;

	for (int i = 0; i != N; ++i)
	{
		int minValueIndex = i;
		for (int j = i + 1; j< N; ++j)
		{
			minValueIndex = arr[j] < arr[minValueIndex] ? j : minValueIndex;
		}
		Swap(arr, i, minValueIndex);
	}
}

void test01()
{
	int ar[] = { 1,6,3,33,5,66,2,3,4,6,8 };
	int i = sizeof(ar) / sizeof(ar[0]);
	printarr(ar,i);
	selectSort(ar,i);
	printarr(ar,i);

}
int main()
{
	test01();
}

冒泡排序

#include <iostream>
using namespace std;
void Swap(int arr[], int i, int j)
{
	int temp = arr[j];
	 arr[j] = arr[i];
	 arr[i] = temp;
}

void printarr(int arr[],int x)
{

	for (int i = 0; i < x; ++i)
	{
		cout << arr[i] <<" ";
	}
	cout << endl;
}

void bubbleeSort(int arr[], int x)
{
	int N = x;
	if (arr == NULL)
	{
		return;
	}

	for (int end = N - 1; end >= 0; end--)
	{
	//0~n-1
	//0~n-2
	//0~n-3
		for (int second = 1; second <= end; ++second)
		{
			if (arr[second - 1] > arr[second])
			{
				Swap(arr,second-1,second);
			}
		}
	}
}

void test01()
{
	int ar[] = { 1,6,3,33,5,66,2,3,4,6,8 };
	int i = sizeof(ar) / sizeof(ar[0]);
	printarr(ar,i);
	//selectSort(ar,i);
	bubbleeSort(ar,i);
	printarr(ar,i);

}

插入排序

void insertSort(int arr[], int x)
{
	int N = x;
	if (arr == NULL)
	{
		return;
	}

	for (int end = 1; end < N; ++end)
	{
		int newNumINdex = end;
		while (newNumINdex - 1 >= 0 && arr[newNumINdex - 1] > arr[newNumINdex])
		{
			Swap(arr, newNumINdex - 1, newNumINdex);
			newNumINdex--;
		}
	}
}

void insertSort2(int arr[], int x)
{
	int N = x;
	if (arr == NULL)
	{
		return;
	}

	for (int end = 1; end < N; ++end)
	{
		// 比如你end现在在 5号位置， pre在5-1位置
		//判断条件是pre下标没有越界并且，pre当前的位置的数字大于pre+1的位置，则交换位置
		//pre--之后，就是4号位置，判断条件是pre下标没有越界并且，pre当前的位置的数字大于pre+1的位置，则交换位置
		for (int pre = end-1; pre >= 0 && arr[pre] > arr[pre + 1]; pre--)
		{
			Swap(arr, pre, pre - 1);
	   }
	}
}