break;
}
}
arr[j+gap]=temp;
}
}
} while (gap>1);
}
// Shell Sort 2
void ShellSort2(int *arr,int length)
{
int gap=length;
do
{
gap=gap/3+1;
for (int i=0+gap;i
if (arr[i]
int temp=arr[i];
int j=i-gap;
do
{
arr[j+gap]=arr[j];
j=j-gap;
} while (j>=0&&temp
}
}
} while (gap>1);
}
// Bubble Sort
void BubbleSort(int *arr,int length)
{
bool exchange=false;
for (int i=0;i
exchange=false;
for (int j=length-1;j>=i+1;j--)
{
if (arr[j]
exchange=true;
int temp=arr[j-1];
arr[j-1]=arr[j];
arr[j]=temp;
}
}
if (exchange==false)
{
return;
}
}
}
// Quick Sort
void QuickSort(int *arr, int low, int high)
{
if (low
int pivocLoc=Partition(arr,low,high);
QuickSort(arr,low,pivocLoc-1);
QuickSort(arr,pivocLoc+1,high);
}
}
// Partition
int Partition(int *arr, int low, int high)
{
int pivotKey=arr[low]; // 记录枢轴
while(low
while(low
int temp=arr[high];arr[high]=arr[low];arr[low]=temp;
while(low
}
return low;
}
// Simple Selection Sort
void SimpleSelectionSort(int *arr, int length)
{
//
for (int i=0;i
int index=i;
if (arr[j]
index=j;
}
}
if(index!=i)
{
// exchange
int temp=arr[i];
arr[i]=arr[index];
arr[index]=temp;
}
}
}
// Heap Sort,小根堆
void HeapSort(int *arr,int length)
{
// 调整数组生成小根堆
for (int i=length/2;i>=1;i--)
{
HeapAdjust(arr,i,length);
}
for (int i=length;i>1;--i)
{
// 交换堆头的元素和最后一个
int temp=arr[1];
arr[1]=arr[i];
arr[i]=temp;
// 重新调整堆为小根堆
HeapAdjust(arr,1,i-1);
}
}
// HeapAdjust
void HeapAdjust(int *arr, int s,int end)
{
int rloc=arr[s];
for (int j=2*s;j<=end;j=j*2)
{
if (j
{
j++; // 找到两个兄弟节点中最小的节点
}
if (!(arr[j]
break;
}
arr[s]=arr[j];
s=j;
}
arr[s]=rloc;
}
// Merge Sort
void MergeSort(int *arr, int *arr2, int left, int right)
{
if (left==right)
{
arr2[left]=arr[left];
return;
}
if (left
int mid=(left+right)/2;
MergeSort(arr,arr2,left,mid);
MergeSort(arr,arr2,mid+1,right);
Merge(arr,arr2,left,mid,right);
}
}
// Merge Array
void Merge(int *arr, int *arr2, int left, int mid, int right)
{
// 将数组保存到暂存空间中
for (int k=left;k<=right;k++)
{
arr2[k]=arr[k];
}
int s1=left;
int s2=mid+1;
int t=left;
while(s1<=mid&&s2<=right)
{
if (arr2[s1]<=arr2[s2])
{
ar