1.概念：升序 降序
2.排序算法的穩(wěn)定性
3.不需要比較的排序：位圖 哈希(直接定址法--找出字符串中第一個(gè)只出現(xiàn)一次的字符)
4.內(nèi)部排序：數(shù)據(jù)可以一次性加載到內(nèi)存中
外部排序：數(shù)據(jù)不能一次性加載到內(nèi)存中
必須掌握：排序原理 代碼 時(shí)間復(fù)雜度 空間復(fù)雜度 穩(wěn)定性 應(yīng)用場(chǎng)景
常見排序算法
插入排序: 數(shù)據(jù)量小 盡可能有序 穩(wěn)定 時(shí)間復(fù)雜度0(n^2) 空間復(fù)雜度0(1)
插入排序.png
//插入排序：數(shù)據(jù)量小 盡可能有序 穩(wěn)定 時(shí)間復(fù)雜度0(n^2) 空間復(fù)雜度0(1)
void InsertSort(int array[], int size)
{
//默認(rèn)已有一個(gè)數(shù)據(jù)
for (int i = 1; i < size; i++)
{
int key = array[i];
int end = i - 1;
//找待插入元素的位置 & 搬移數(shù)據(jù)
while (end >= 0 && key < array[end])
{
array[end + 1] = array[end];
end--;
}
//插入數(shù)據(jù)
array[end + 1] = key;
}
}
void TestInsertSort()
{
int array[] = { 2, 5, 4, 9, 3, 6, 8, 7, 1, 0 };
InsertSort(array, sizeof(array) / sizeof(array[0]));
}
插入排序調(diào)試1.png
插入排序2.png
希爾排序:
時(shí)間0(n1.25)or0(n1.65) 空間0(1) 不穩(wěn)定：間隔元素排序榛搔，不穩(wěn)定 應(yīng)用場(chǎng)景：數(shù)據(jù)量大且雜亂祸泪。
希爾排序.png
void ShellSort(int array[], int size)
{
int gap = 3;
while (gap > 0)
{
for (int i = gap; i < size; i++)
{
int key = array[i];
int end = i - gap;
//找待插入元素的位置 & 搬移數(shù)據(jù) (找位置嘗試二分查找癣朗。)
while (end >= 0 && key < array[end])
{
array[end + gap] = array[end];
end-=gap;
}
//插入數(shù)據(jù)
array[end + gap] = key;
}
gap--;
}
}
void TestShellSort()
{
int array[] = { 2, 5, 4, 9, 3, 6, 8, 7, 1, 0 };
InsertSort(array, sizeof(array) / sizeof(array[0]));
}
希爾排序調(diào)試1.png
希爾排序調(diào)試2.png
選擇排序
選擇排序.png
//選擇排序
void Swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
void SelectSort(int *array, int size)
{
for (int i = 0; i < size - 1; i++)
{
int maxPos = 0;
for (int j = 1; j < size-i; j++)
{
if (array[j]>array[maxPos])
maxPos = j;
}
if (maxPos!=size-i-1) //最大的元素在最后（升序） 則不需要交換
Swap(&array[size - 1-i], &array[maxPos]);
}
}
選擇排序1.png
選擇排序2.png
選擇排序優(yōu)化
void SelectSort_OP(int *array, int size)
{
int begin = 0;
int end = size - 1;
while (begin < end)
{
int minPos = begin;
int maxPos = end;
//找最大 最小元素位置
int i = begin + 1;
while (i <= end)
{
if (array[i]>array[maxPos])
maxPos = i;
if (array[i] < array[minPos])
minPos = i;
i++;
}
if (maxPos != end)
Swap(&array[maxPos], &array[end]);
//最小的元素有可能在end的位置 需要重新標(biāo)記minPos
if (minPos == end)
minPos = maxPos;
if (minPos != begin)
Swap(&array[minPos], &array[begin]);
begin++;
end--;
}
}
void TestSelectSort()
{
int array[] = { 2, 5, 4, 9, 3, 6, 8, 7, 1, 0 };
SelectSort_OP(array, sizeof(array) / sizeof(array[0]));
}
選擇排序優(yōu)化.png
選擇排序優(yōu)化2.png
冒泡排序
//冒泡排序
void BubbleSort(int *array, int size)
{
for (int i = 0; i < size - 1; i++)
{
for (int j = 0; j < size - i-1; j++)
{
if (array[j]>array[j + 1])
Swap(&array[j], &array[j + 1]);
}
}
}
void TestBubbleSort()
{
int array[] = { 2, 5, 4, 9, 3, 6, 8, 7, 1, 0 };
BubbleSort(array, sizeof(array) / sizeof(array[0]));
}
冒泡排序1.png
冒泡排序2.png
