//插入排序
void InsertSort(int array[], int size)
{
for (int i=1;i<size;i++)
{
int end = i - 1;
int key = array[i];
//寻找插入位置
while (end>=0&&array[end]>key)
{
array[end+1] = array[end];
end--;
}
//插入元素
array[end + 1] = key;
}
}? a. 元素集合越接近有序，直接插入排序算法的时间效率越高
? b. 时间复杂度：O(N^2)
? c.空间复杂度：O(1)，它是一种稳定的排序算法
? d. 稳定性：稳定
//希尔排序
void ShellSort(int array[], int size)
{
int gap = size;
while (gap > 1)
{
gap = gap / 3 + 1;
for (int i = gap; i < size; i++)
{
int end = i - gap;
int key = array[i];
while (end>=0&&array[end]>key)
{
array[end+gap] = array[end];
end=end-gap;
}
array[end + gap] = key;
}
}
}? a. 希尔排序是对直接插入排序的优化
? b. 希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度： O(N^1.3—N^2）
? c.稳定性：不稳定
void swap(int arr1[], int arr2[])
{
int temp = 0;
temp = *arr1;
*arr1 = *arr2;
*arr2 = temp;
}
//选择排序
void SelectSort(int array[], int size)
{
for(int i=0;i<size-1;i++)//最后剩一个数就不用排了，因此是size-1
{
int maxPos = 0;
//寻找最大值的位置
for (int j = 1; j < size - i; j++)
{
if (array[j] > array[maxPos])
{
maxPos = j;
}
}
//将最大值放在数组最后
if (maxPos != size - 1 - i)
{
swap(&array[maxPos], &array[size - 1 - i]);
}
}
}//选择排序另一种方法
void SelectSortOP(int array[], int size)
{
int begin = 0,end = size - 1;
while (begin < end)
{
//找最大最小元素位置
int maxPos = begin;
int minPos = begin;
int index = begin + 1;
while (index <= end)
{
if (array[index] > array[maxPos])
{
maxPos = index;
}
if (array[index] < array[minPos])
{
minPos = index;
}
index++;
}
if (maxPos != end)
{
swap(&array[maxPos], &array[end]);
}
//如果最小的元素恰巧在end处，则上面操作会改变最小元素的位置
if (minPos == end)
{
minPos = maxPos;
}
if (minPos != begin)
{
swap(&array[minPos], &array[begin]);
}
begin++;
end--;
}
}? a.直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
? b.时间复杂度：O(N^2)
? c.空间复杂度：O(1)
? d.稳定性：不稳定
void swap(int arr1[], int arr2[])
{
int temp = 0;
temp = *arr1;
*arr1 = *arr2;
*arr2 = temp;
}
//向下调整算法
void HeapAdjust(int array[], int size, int parent)
{
//先标记左孩子，parent可能有左没有右
int child = parent * 2 + 1;
while (child<size)
{
//找到左右孩子中较大的，用child标记
if (child+1 < size && array[child] < array[child + 1])
{
child += 1;
}
//如果双亲结点小于较大的子结点，则交换
if (array[parent] < array[child])
{
swap(&array[parent], &array[child]);
parent = child;
child = parent * 2 + 1;
}
else
{
return;
}
}
}
//堆排序
void HeapSort(int array[], int size)
{
int end = size - 1;
//建堆， 升序-->大堆 降序-->小堆
//从倒数第一个非叶子结点到根结点一直向下调整
for (int root = (end - 1) / 2; root >= 0; root--)
{
HeapAdjust(array, size, root);
}
//排序
while(end)
{
swap(&array[0], &array[end]);
HeapAdjust(array, end , 0);
end--;
}
}? a.堆排序使用堆来选数，效率就高了很多
? b.时间复杂度：O(N*logN)
? c.空间复杂度：O(1)
? d.稳定性：不稳定
//冒泡排序
void BubbleSort(int array[], int size)
{
for (int i = 0; i < size - 1; i++)
{
int flag=0;
//相邻两个元素比较，不满足就交换
for (int j = 0; j < size - i-1; j++)
{
if (array[j]>array[j+1])
{
flag=1;
swap(&array[j] ,&array[j+1]);
}
}
if(!flag)//如果flag为0，则没有发生交换，则数组已经有序，就不用再比较了
{
return;
}
}
}? a.时间复杂度：O(N^2)
? b.空间复杂度：O(1)
? c.稳定性：稳定
//计数排序
void CountSort(int array[], int size)
{
//1.找数据范围
int max = array[0];
int min = array[0];
int index = 0;
for (int i = 0; i < size; i++)
{
if (array[i] > max)
{
max = array[i];
}
if (array[i] < min)
{
min = array[i];
}
}
//2.申请空间
int* count = (int*)calloc(max - min + 1, sizeof(int));
if (NULL == count)
{
return NULL;
}
//3.统计每个元素出现次数
for (int i = 0; i < size; i++)
{
count[array[i] - min]++;
}
//4.array数组排序
for (int i=0;i<max-min+1;i++)
{
while (count[i]--)
{
array[index++] = i + min;
}
}
free(count);
}? a. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限
? b. 时间复杂度：O(MAX(N,范围))
? c. 空间复杂度：O(范围)
? d. 稳定性：稳定
//第一种：hoare法
int Partion1(int array[], int left, int right)
{
int begin = left;
int end = right - 1;
int key = array[end];//基准值是最后一个元素
while (begin < end)
{
while (begin<end&&array[begin] <= key) //保证有效区间
{
begin++;
}
while (begin < end&&array[end] >= key)
{
end--;
}
if (begin < end)
{
swap(&array[begin], &array[end]);
}
}
if (begin!=right-1)
{
swap(&array[begin], &array[right - 1]);//将基准值放在数组中间
}
return begin;//返回基准值位置
}
//第二种：挖坑法
int Partion2(int array[], int left, int right)
{
int begin = left;
int end = right - 1;
int key = array[end];
while (begin < end)
{
//begin从前往后找，找比基准值大的元素
while (begin < end&&array[begin] <= key)
{
begin++;
}
if (begin < end)
{
array[end] = array[begin];
end--;
}
while (begin < end&&array[end] >= key)
{
end--;
}
if (begin < end)
{
array[begin] = array[end];
begin++;
}
}
array[begin] = key;
return begin;
}
//第三种
int Partion3(int array[], int left, int right)
{
int cur = left;
int prev = cur-1;
int key = array[right - 1];
while (cur < right)
{
if (array[cur] < key&&++prev != cur)
{
swap(&array[cur], &array[prev]);
}
cur++;
}
if (++prev != right - 1)//将基准值放在正确的位置
{
swap(&array[prev], &array[right-1]);
}
return prev;
}
void QuickSort(int array[], int left, int right)
{
int div = 0;
if (right - left <= 1)
{
return;
}
//找基准值对区间中的数据进行划分，div表述划分好等候基准值位置
div = Partion3(array, left, right);
//递归
QuickSort(array, left, div);
QuickSort(array, div+1, right);
}? a. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
? b. 时间复杂度：O(N*logN)
? c. 空间复杂度：O(logN)
? d. 稳定性：不稳定
//合并两个有序数组
void MergeData(int array[], int left, int mid, int right, int temp[])
{
int begin1 = left, end1 = mid;
int begin2 = mid , end2 = right;
int index = left;
while (begin1 < end1 && begin2 < end2)
{
if (array[begin1] <= array[begin2])
{
temp[index++] = array[begin1++];
}
else
{
temp[index++] = array[begin2++];
}
}
while (begin1<end1)
{
temp[index++] = array[begin1++];
}
while (begin2 < end2)
{
temp[index++] = array[begin2++];
}
}
//归并排序
void MergeSort(int array[], int left, int right, int temp[])
{
if (right - left <= 1)
{
return;
}
int mid = left + ((right - left) / 2);
MergeSort(array, left, mid, temp);
MergeSort(array,mid , right, temp);
MergeData(array, left, mid, right, temp);
memcpy(array + left, temp+left, sizeof(array[0])*(right - left));
}
? a. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
? b. 时间复杂度：O(N*logN)
? c. 空间复杂度：O(N)
? d. 稳定性：稳定
原文：https://blog.51cto.com/u_15153653/2855818