1.直接插入排序 O(N*N)
void solution(int array[],int size)
{
for (int i = 0; i < size-1; ++i)
{
int temp = array[i+1];
int end = i;
while (end>=0 && array[end]>temp)
{
array[end+1] = array[end];
end--;
}
array[end+1] = temp;
}
}
2.二分查找直接插入排序 、折半插入排序
void solution(int array[], int size)
{
for (int i = 0; i < size - 1; ++i) //這裡i從零開始是為了更好的貼近數組下标
{
int temp = array[i + 1];
int end = i;
int left = 0;
int right = end;
while(left<=right)
{
int mid = left + ((right - left) >> 1);
if (array[mid] > temp)
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
while (end>=0&&end >= left)
{
array[end + 1] = array[end];
end--;
}
array[end + 1] = temp;//要是上面while沒有執行 則此時temp還是end+1的值 這一步相當于沒有做
}
}
3.希爾排序
void solution(int array[],int size)
{
int gap = size;
while (gap >= 1) //這裡必須為>=1 因為可能最後間隔為1排
{
gap = gap / 3 + 1;
for (int i = gap; i < size; ++i)
{
int temp = array[i]; //這裡temp為gap下标的值
int end = i - gap;
while (end >= 0 && array[end]>temp)
{
array[end + gap] = array[end];
end -= gap;
}
array[end+gap] = temp;
}
gap--;
}
}