数据结构和排序

数据分为

物理结构

顺序存储结构
- 连续
链式存储结构
- 数据任意存储单元，通过保存地址方式找到关联数据元素

队列的定义

队列：一头压入，另一头弹出，先进先出
栈：只能栈顶插入和删除，先进后出
排序
选择、冒泡、插入
归并、快速、

// test01.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <string>

using namespace std;

class Solution
{
public:
	/* 
快速排序原理
	利用双指针将小数放在左边，大数放在右边
编程思路
	选定左右指针（left、right）和基数（basic），基数随机设为left对应的值
	right探测小于basic，停下来准备和left交换（找大数）
	left探测大于basic，停下来和right交换（找小数）
	right继续探测直到小于basic，直到遇到left
	left继续探测直到大于basic，直到遇到right
	若两则相遇，则将相遇的数(i或j)与基数（basic）交换，到此时完成一次循环。
	将离散数列分成两部分左边小于基数，右边大于基数

	递归左右两边继续快排
	time: O(NlogN)  ？？？？？
	Space: O(logN)  递归的层数，每层存取的临时变量
	不稳定
	*/
	int Partion(int* arr, int left_bound, int right_bound)
	{
		if(left_bound >= right_bound) return -1;
		int left = left_bound;
		int right = right_bound;
		int pivot = arr[left_bound];

		while(left < right)
		{
			while(arr[right] >= pivot && left < right) right--;
			while(arr[left] <= pivot && left < right) left++;
			if(left < right)
				swap(arr[left], arr[right]);
		}
		swap(arr[left_bound], arr[left]);
		return left;
	}

	int QuickSort(int* arr, int left_bound, int right_bound)
	{
		if(left_bound >= right_bound) return -1;
		int pivot_ptr = Partion(arr, left_bound, right_bound);
		QuickSort(arr, left_bound, pivot_ptr-1);
		QuickSort(arr, pivot_ptr+1, right_bound);
		return 0;
	}
	/*
		选择：遍历所有元素，找到最小元素的下标，再放到前面去
		O(n^2) O(1) 不稳定
	*/
	void choiceSort(int arr[], int arrSize)
	{
		for (int i = 0; i < arrSize; i++)
		{
			int minIndex = i;
			for (int j = i + 1; j < arrSize; j++)
				minIndex = (arr[j] < arr[minIndex]) ? j : minIndex;
			swap(arr[i], arr[minIndex]);
		}
	}
	/* 原理：相邻两两比较，大的换到后面去
	 * time : O（N^2）
	 * space: O(1)
	*/
	void bubbleSort(int arr[], int ArrSize)
	{
		for (int i = 0; i < ArrSize - 1; i++)
			for (int j = 0; j + i < ArrSize - 1; j++)	//每一趟少循环一次
				if (arr[j] > arr[j + 1])
					swap(arr[j], arr[j + 1]);
	}

	/* 插入:抓牌从后往前比较，把小的放前面
	 * time: o(n^2)
	 * space：O(1) 
	 * 稳定
	 */
	void insertSort(int arr[], int ArrSize)
	{
		for (int i = 1; i < ArrSize; i++) 
			for (int j = i; j > 0; j--)
				if(arr[j] < arr[j - 1])
					swap(arr[j], arr[j - 1]);
	}

	/* 归并“治”思想：将两个有序区间，排成一个有序区间 
	 *	两边比较末端最小值，收到容器里
	 */
	void mergeAdd(int arr[], int left, int mid, int right, int* temp) //实现“治”
	{
		int i = left;
		int j = mid + 1;
		int k = left;
		//小数放到temp中
		while (i <= mid && j <= right)
			temp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
		//没放完
		while (i <= mid)
			temp[k++] = arr[i++]; 
		//没放完
		while (j <= right)
			temp[k++] = arr[j++];

		memcpy(arr + left, temp + left, sizeof(int) * (right - left + 1));
	}

	/* 归并分：取中间轴分成两个区域
	 *		对新的区域再进行分割
	 *   O(nlogn)  O(n)  稳定
	 */
	void mergeSort(int arr[], int left, int right, int* temp) {//实现“分”
		if (left >= right)
			return;

		int mid = left + (right - left) / 2;
		/* 分：左右两个区间【left, mid】 【mid+1,right】 */
		mergeSort(arr, left, mid, temp);
		mergeSort(arr, mid + 1, right, temp);
		/* 治：两边对比拿小的,全拿 */
		mergeAdd(arr, left, mid, right, temp);
		return;
	}


};

int _tmain(int argc, _TCHAR* argv[])
{
	int arr[] = {1, 5, 2, 4, 3};
	
	Solution s;
	//s.QuickSort(arr, 0, 4);
	//s.choiceSort(arr, 5);
	//s.bubbleSort(arr, 5);
	//s.insertSort(arr, 5);
	int temp[5] = {0};
	s.mergeSort(arr, 0, 4, temp);

	for(int i=0; i<5; i++)
		cout << arr[i] << endl;
	for(int i=0; i<5; i++)
		cout << temp[i] << endl;
	system("PAUSE");
	return 0;
}

参考
https://blog.csdn.net/yushiyi6453/article/details/76407640?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.nonecase