关于排序的总结

• 冒泡排序
• 选择排序
• 快速排序
• 希尔排序：
• 堆排序

void BubbleSort(int arr[],int len)
{
	for (int i = 0; i < len - 1; i++)
	{
		for (int j = 0; j < len - 1 - i; j++)
		{
			if (arr[j] > arr[j+1])
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}
}

void SelectSort(int arr[], int len)
{
	for (int i = 0; i < len - 1; i++)
	{
		int min = i;
		for (int j = i + 1; j < len; j++)
		{
			if (arr[min] > arr[j])
			{
				min = j;
			}
		}
		int temp = arr[i];
		arr[i] = arr[min];
		arr[min] = temp;
	}
}

void QuickSort(int arr[], int begin, int end)
{
	if (begin > end)
	{
		return;
	}
	int temp = arr[begin];
	int i = begin, j = end;
	while (i != j)
	{
		while (arr[j] >= temp && j > i)
		{
			j--;
		}
		while (arr[i] <= temp && j > i)
		{
			i++;
		}
		if (j > i)
		{
			int t = arr[i];
			arr[i] = arr[j];
			arr[j] = t;
		}
	}
	arr[begin] = arr[i];
	arr[i] = temp;
	QuickSort(arr, begin, i - 1);
	QuickSort(arr, i + 1, end);
}

void ShellInsert(vector&s, int gap)
{
	for (int i = gap; i < s.size(); i++)
	{
		for (int j = i-gap; j >=0 ; j-=gap)
		{
			if (s[j] > s[j + gap])
			{
				int temp = s[j + gap];
				s[j + gap] = s[j];
				s[j] = temp;
			}
			else
			{
				break;
			}
		}
	}
}

void adjust(int arr[], int len, int index)//index是父亲结点的下标，该函数用来将数组修改为最大堆
{
	int left = 2 * index + 1;//左子树下标
	int right = 2 * index + 2;//右子树下标
	int maxindex = index;
	if (left < len && arr[left] > arr[maxindex])
	{
		maxindex = left;
	}
	if (right < len && arr[right] > arr[maxindex])
	{
		maxindex = right;
	}//maxindex是三个下标中对应数值最大的那个

	if (maxindex != index)//如果maxindex有改变
	{
		swap(arr[maxindex], arr[index]);
		adjust(arr, len, maxindex);
	}
}
void HeapSort(int arr[], int size)
{
	for (int i = size/2 - 1; i >=0; i--)//最后一个结点是len-1，其父亲结点就是size/2-1
	{
		adjust(arr, size, i);
	}
	for (int i = 0; i < size; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
	for (int i = size - 1; i >= 1; i--)
	{
		swap(arr[0], arr[i]);//交换顶端的结点和末尾的结点，然后重构最大堆
		adjust(arr, i, 0);
		for (int i = 0; i < size; i++)
		{
			cout << arr[i] << " ";
		}
		cout << endl;
	}
}