정렬 삽입, 힐 정렬, 거품 정렬, 빠 른 정렬, 정렬 선택, 정렬 쌓 기 (상세 설명)

   #include
#include

using namespace std;

void InsertSort(int *arr,int sz)//    
{
	for (int i = 0; i < sz-1; i++)
	{
		int end = i;
		int key = arr[end + 1];
		while (end >= 0)
		{
			if (arr[end] > key)
			{
				arr[end + 1] = arr[end];
				--end;
			}
			else
				break;
		}
		arr[++end] = key;
	}
}

void ShellSort(int *arr,int s)//    
{
	int gap = s;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < s - gap ;i++)
		{
			int end = i;
			int key = arr[end+gap];
			while (end>0)
			{
				if (arr[end] > key)
				{
					arr[end + gap] = arr[end];
					end = end - gap;
				}
				else
					break;
			}
			arr[end+gap] = key;
		}
		
	}
}

void Swap(int &a, int &b)
{
	if (a > b)
	{
		int temp = a;
		a = b;
		b = temp;
	}
}

void Bubble(int *arr, int sz)//     
{
	for (int i = 0; i < sz - 1; i++)
	{
		for (int j = i + 1; j < sz ; j++)
		{
			if (arr[i]>arr[j])
				Swap(arr[i], arr[j]);
		}
	}
}

void Bubble1(int *arr, int sz)//    
{
	for (int i = 0; i < sz - 1; ++i)
	{
		for (int j = 0; j < sz-1-i; ++j)//    sz-1-i ，      sz-1 ，arr[j]       ，arr[j+1]      ，
		{
			if(arr[j]>arr[j+1])
			Swap(arr[j],arr[j+1]);
		}
	}
}

void Bubble2(int *arr, int sz)//          ，          
{
	/*mark   arr2[]        ，        ，      。   Bubble1   ，              ，      。 Bubble2  mark，          ，           ，mark      0，             ，  mark=0，       ，          。               。*/
	int mark = 1;
	for (int i = 0; i < sz - 1&&mark; ++i)
	{
		mark = 0;
		for (int j = 0; j < sz - 1 - i; ++j)
		{
			if (arr[j]>arr[j + 1])
			{
				Swap(arr[j], arr[j + 1]);
				mark = 1;
			}
		}
	}
}

void QuickSort(int *arr,int left,int right)//    ，     
{
	int key = right;
	int begin = left;
	int end = right;
	while (left >= right)
	{
		return;
	}
	while (left < right)
	{
		while (left < right&&arr[left] <= arr[key])
			left++;
		while (left < right&&arr[right] >= arr[key])
			right--;
		if (left < right&&arr[left] != arr[right])
		{
			Swap(arr[left], arr[right]);
		}
	}
	
	Swap(arr[left],arr[key]);
	QuickSort(arr, begin, left - 1);//     key         ，right=key=key     ，begin=key       。
	QuickSort(arr,left+1,end);//     key          ，begin=  key          ，key=right=       
}

void QuickSort1(int *arr, int left, int right)//    ，   
{
	while (left >= right)
		return;

	int hollow = right;
	int begin = left;
	int end = right;
	int key = arr[right];
	
	while (left < right)
	{
		while (left < right&&arr[left] <= key)
			left++;
		arr[hollow] = arr[left];
		hollow = left;

		while (left < right&&arr[right] >= key)
			right--;
		arr[hollow] = arr[right];
		hollow = right;
		
	}
	if (left == right)
	{
		arr[left] = key;
	}
	QuickSort1(arr, begin, left - 1);
	QuickSort1(arr, left + 1, end);
}

/*
void QuickSort2(int *arr, int left, int right)//     ,     
{
	while (left >= right)
		return;
	int hollow = right;
	int begin = left;
	int end = right;
	int key = arr[right];
	while (left < right)
	{
		while (left < right&&arr[left] < key)
			left++;
		Swap(arr[hollow], arr[left]);
		hollow = left;
		while (leftkey)
			right--;
		Swap(arr[hollow], arr[right]);
		hollow = right;
	}
	QuickSort2(arr, begin, left - 1);
	QuickSort2(arr, left + 1, end);

}
*/

void SelectSort(int *arr, int sz)//    
{
	int i, j, min;
	for (i = 0; i < sz; ++i)
	{
		min = i;
		for (j = i + 1; j < sz; ++j)
	/*i=0     ， i=0                 ，      ，      min，      ，      ，  min。               。  ，i=1      ， i=1                 ，      ，      min，      ，      ，  min。               。    。。。。*/
		{
			if (arr[j] < arr[min])
				min = j;
		}
		//if (min != i)//      ，         ，                    。
			Swap(arr[i], arr[min]);
	}
}

void AdjustDown(int *arr,int father,int sz)//    （     ）
{
	int child = father * 2 + 1;
	while (child < sz)
	{
		if (child + 1 < sz&&arr[child + 1] > arr[child])//                
		{
			child++;
		}
		if (arr[child]>arr[father])
		{
			Swap(arr[child], arr[father]);
			father = child;
			child = father * 2 + 1;
		}
		else
			return;
	}
}

void AdjustUp(int *arr, int father, int sz)//    （  ）
{
	int child = father * 2 + 1;
	while (child < sz)
	{
		if (child + 1 < sz&&arr[child] > arr[child + 1])
			child++;
		if (arr[child] < arr[father])
		{
			swap(arr[child], arr[father]);
			father = child;
			child = father * 2 + 1;
		}
		else
			return;
	}
}

void HeapSort(int *arr, int sz)//   
{
	int i = 0;
	for (i = (sz - 2) / 2; i >= 0; i--)
	{
		AdjustDown(arr, i, sz);//   ，  
	}
	while (sz > 1)
	{
		sz--;
		swap(arr[0], arr[sz]);//            ，          ，        。     
		AdjustDown(arr, 0, sz);
	}
}

void HeapSort1(int *arr, int sz)//   ，
{
	int i = 0;
	for (i = (sz - 2) / 2; i >= 0; i--)
	{
		AdjustUp(arr, i, sz);//   ，  
	}
	while (sz > 1)
	{
		sz--;
		swap(arr[0], arr[sz]);//            ，         ，        。     。
		AdjustUp(arr, 0, sz);
	}
}

void Merge(int *arr, int *temp, int begin1, int end1, int begin2, int end2)//    
{
	int pos = begin1;//pos               
	int index = begin1;//index                 
	while (begin1 <= end1&&begin2 <= end2)//            ，         
	{
		if (arr[begin1] < arr[begin2])
			temp[index++] = arr[begin1++];
		else
			temp[index++] = arr[begin2++];
	}
	while (begin1 <= end1)//           
	{
		temp[index++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		temp[index++] = arr[begin2++];
	}
	memcpy(arr + pos, temp + pos, sizeof(int)*(end2 - pos + 1));// temp+pos              ，  （end2-pos+1）         arr+pos             
}

void _Merge(int *arr,int *temp,int left,int right)//    
{
	if (left >= right)
		return;
	int mid = left + (right - left) / 2;
	_Merge(arr,temp,left,mid);//    
	_Merge(arr, temp, mid+1, right);//    
	Merge(arr,temp,left,mid,mid+1,right);//    
}

void MerageSort(int *arr, int sz)//    
{
	int *tmp = new int[sz];
	_Merge(arr, tmp, 0, sz - 1);
	delete []tmp;
}

void Print(int *arr, int sz)
{
	for (int i = 0; i < sz; i++)
		cout << arr[i] << ' ';
	cout << endl;
}

int main()
{
	int arr[] = { 5, 7, 6, 4, 9, 2, 8, 1, 3};
	int arr1[] = { 10, 90, 40, 54, 63, 78, 11, 52, 45, 65, 79 };
	int arr2[] = {9,1,2,3,4,5,6,7,8};
	int arr3[] = {9,8,7,6,5,4,3,2,1,0};
	int arr4[] = {90, 10, 50, 80, 30, 70, 40, 60, 20};
	int arr_4[] = { 90, 10, 50, 80, 30, 70, 40, 60, 20 };
	int arr5[] = {10,30,50,20,90,60,80,70,40};
	//cout << "    ：";
	//int sz = sizeof(arr) / sizeof(arr[0]);
	//InsertSort(arr, sz);//    
	//Print(arr, sz);
	//Bubble2(arr2, sz);//    
	//Print(arr2, sz);

	cout << "    ：";
	int sz1 = sizeof(arr1) / sizeof(arr1[0]);
	ShellSort(arr1, sz1);//    
	Print(arr1, sz1);

	cout << "    ：";
	int sz = sizeof(arr) / sizeof(arr[0]);
	QuickSort(arr, 0,sz-1);//    
	Print(arr, sz);

	cout << "    ：";
	int sz3 = sizeof(arr3) / sizeof(arr3[0]);
	SelectSort(arr3, sz3);
	Print(arr3, sz3);

	cout << "   ：";
	int sz4 = sizeof(arr4) / sizeof(arr4[0]);
	HeapSort(arr4, sz4);//   ，    
	Print(arr4,sz4);

	cout << "（ ）   ：";
	int sz_4 = sizeof(arr_4) / sizeof(arr_4[0]);
	HeapSort1(arr_4, sz_4);//    ，    
	Print(arr_4, sz_4);


	cout << "    ：";
	int sz5 = sizeof(arr5) / sizeof(arr5[0]);
	MerageSort(arr5, sz5);
	Print(arr5,sz5);

	system("pause");
	return 0;
}