void BubbleSort(int arr[],int size)
{
assert(arr);
int iBeign = 0;
int jBeign = 0;
int flag = 1;
int temp = 0;
for (iBeign = 1; (iBeign < size) && (flag == 1);iBeign++)
{
flag = 0;
for (jBeign = 0; jBeign < size - iBeign; jBeign++)
{
if (arr[jBeign] > arr[jBeign + 1])
{
flag = 1;
temp = arr[jBeign];
arr[jBeign] = arr[jBeign + 1];
arr[jBeign + 1] = temp;
}
}
}
}
void SelectSort(int arr[], int size)
{
assert(arr);
int iBeign = 0;
int jBeign = 0;
int Small= 0;
int temp = 0;
for (iBeign = 0; iBeign < size; iBeign++)
{
Small = iBeign;
for (jBeign = iBeign + 1; jBeign < size; jBeign++)
{
if (arr[jBeign] < arr[Small])
{
Small = jBeign;
}
}
if (Small != iBeign)
{
temp = arr[Small];
arr[Small] = arr[iBeign];
arr[iBeign] = temp;
}
}
}
void InsertSort(int arr[], int size)
{
assert(arr);
int iBeign = 0;
int jBeign = 0;
int key = 0;
for (iBeign = 1; iBeign < size; iBeign++)
{
key = arr[iBeign];
jBeign = iBeign - 1;
while ( (jBeign >= 0 ) && (key < arr[jBeign]) )
{
arr[jBeign + 1] = arr[jBeign];
arr[jBeign] = key;
jBeign--;
}
}
}
void Quick(int arr[], int low,int high) //一趟快排
{
assert(arr);
int i = low;
int j = high;
int key = arr[low];
while (i < j)
{
while ((i < j) && (key < arr[j]))
{
j--;
}
if (i < j)
{
arr[i] = arr[j];
i++;
}
while ((i < j) && (key > arr[i]))
{
i++;
}
if (i < j)
{
arr[j] = arr[i];
j--;
}
}
arr[i] = key;
if (i > low)
{
Quick(arr, low , i - 1);
}
if (j < high)
{
Quick(arr, j + 1, high);
}
}
void QuickSort(int arr[], int size)
{
assert(arr);
Quick(arr, 0, size - 1);
}
int dlta[] = { 5, 3, 2, 1}; //增量序列
void ShellInsert(int arr[] ,int size ,int dk)
{
assert(arr);
int iBegin = 0;
int jBegin = 0;
int key = 0;
for (iBegin = dk; iBegin < size; iBegin++)
{
key = arr[iBegin];
jBegin = iBegin - dk;
while ((jBegin >= 0) && (key < arr[jBegin] ))
{
arr[jBegin + dk] = arr[jBegin];
arr[jBegin] = key;
jBegin -= dk;
}
}
}
void ShellSort(int arr[], int size,int t)
{
int i = 0;
for (i = 0; i < t;i++)
{
ShellInsert(arr, size, dlta[i]);
}
}
void Heapjust(int arr[], int size,int h)
{
assert(arr);
int i = h;
int j = 2 * i + 1;
int key = arr[i];
int flag = 0;
while ( (j < size) && (flag != 1))
{
if ((j < size - 1) && (arr[j] < arr[j + 1])) //建立大堆 注意点1
{
j++;
}
if (key > arr[j]) //注意点2
{
flag = 1;
}
else
{
arr[i] = arr[j];
i = j;
j = 2 * i + 1;
}
}
arr[i] = key;
}
void MinHeapInit(int arr[], int size)
{
assert(arr);
int i = 0;
for (i = (size - 2) / 2; i >= 0; i--)
{
Heapjust(arr, size, i);
}
}
void HeapSort(int arr[], int size)
{
assert(arr);
int i = 0;
int temp = 0;
MinHeapInit(arr, size);
for (i = size - 1; i >= 0; i--)
{
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
Heapjust(arr, i, 0);
}
}
int TR[size] = { 0 }; //辅助归并排序开辟的空间，， 辅助存储 O(n)
//int arr[] TR数组的大小要与要排序数组arr的大小一样
//Merging Sort(2- 路归并排序）
//有序的arr[start,...,mid]和arr[mid+1,...,end]归并为有序的TR[i,...,n]
void Merge(int arr[], int TR[],int start,int mid, int end)
{
assert(arr);
assert(TR);
int iBegin = start;
int jBegin = mid + 1;
int data = 0;
int iTR = start;
while ( (iBegin <= mid) && (jBegin <= end) ) //链表合并思想
{
if (arr[iBegin] > arr[jBegin])
{
data = arr[jBegin];
jBegin++;
}
else
{
data = arr[iBegin];
iBegin++;
}
TR[iTR++] = data;
}
while (iBegin <= mid)
{
TR[iTR++] = arr[iBegin++];
}
while (jBegin <= end)
{
TR[iTR++] = arr[jBegin++];
}
while (--iTR >= start)
{
arr[iTR] = TR[iTR];
}
}
//将arr[start,...,t]归并排序到TR[start,...,t]
void MSort(int arr[], int TR[], int start, int end)
{
assert(arr);
assert(TR);
int mid = 0;
if (start == end)
{
return;
}
else
{
mid = (start + end) / 2;
MSort(arr, TR, start, mid);
MSort(arr, TR, mid + 1, end);
Merge(arr, TR, start, mid, end);
}
}
void MergeSort(int arr[],int TR[], int size)
{
assert(arr);
assert(TR);
MSort(arr, TR, 0, size - 1);
}