//常用的排序算法
include <iostream>
using namespace std;
typedef int ElemType;
/*
1谎僻、插入排序
（1）直接插入排序算法
算法思想：將等排序列劃分為有序與無序兩部分，然后再依次將無序部分插入到已經(jīng)有序的部分争拐，最后
就可以形成有序序列。
操作步驟如下：
1）查找出元素L（i）在表中的插入位置K晦雨；
2）將表中的第K個元素之前的元素依次后移一個位置架曹；
3）將L（i）復(fù)制到L（K）。
時間復(fù)雜度為：O(n^2)
*/
void InsertSort(ElemType arr[], int length)
{
int i, j;
ElemType guard; // 哨兵
for (i = 1; i < length; ++i)
{
if (arr[i] < arr[i-1]) // 在無序部分尋找一個元素闹瞧，使之插入到有序部分后仍然有序
{
guard = arr[i];// 復(fù)制到“哨兵”
// 將第i個元素之前的元素依次后移一個位置
for (j = i - 1; arr[j] > guard; j--)
{
arr[j + 1] = arr[j];
}
arr[j + 1] = guard; // 復(fù)制到插入位置
}
}
}
/*
2绑雄、折半插入排序
使用于排序表為順序存儲的線性表
在查找插入位置時，采用折半查找
算法思想是：
1）設(shè)置折半查找范圍奥邮；
2）折半查找
3）移動元素
4）插入元素
5）繼續(xù)操作1）万牺、2）、3）洽腺、4）步脚粟，直到表成有序。
*/
void BinaryInsertSort(ElemType arr[], int length)
{
int i, j, low, high, mid;
ElemType tmp;
for ( i = 1; i < length; ++i )
{
tmp = arr[i]; // 復(fù)制到哨兵
// 設(shè)置折半查找范圍
low = 0;
high = i;
while (low <= high) // 折半查找
{
mid = (low + high) / 2;
if (arr[mid] > tmp) // 在左半部分查找
{
high = mid - 1;
}
else
{
low = mid + 1; // 在右半部分查找
}
}
// 移動元素
for ( j = i - 1; j >= high + 1; --j )
{
arr[j + 1] = arr[j];
}
arr[j + 1] = tmp;
}
}
/*
3蘸朋、希爾(Shell)排序
基本思想：
先將待排序的表分割成若干個形若L[i, i+d, i+2d, ..., i+kd]的“特殊”子表核无，分別進行直接插入排序，
當(dāng)整個表已呈“基本有序”時度液，再對全體記錄進行一次直接插入排序厕宗。
算法過程：
1）先取一個小于n的步長d1,把表中全部記錄分成d1個組，所有距離為d1的倍數(shù)的記錄放在同一組中堕担，在各
組中進行直接插入排序；
2）然后取第二個步長d2 < d1, 重復(fù)步驟1
3）直到dk = 1曲聂，再進行最后一次直接插入排序
*/
void ShellSort(ElemType arr[], int length)
{
int i, j, dk = length / 2;
ElemType tmp;
while (dk >= 1)// 控制步長
{
for (i = dk; i < length; ++i)
{
if (arr[i] < arr[i - dk])
{
tmp = arr[i]; // 暫存
// 后移
for (j = i - dk; j >= 0 && tmp < arr[j]; j -= dk)
{
arr[j + dk] = arr[j];
}
arr[j + dk] = tmp;
}
}
dk /= 2;
}
}
/*
4霹购、冒泡排序算法
基本思想：
假設(shè)待排序的表長為n， 從后向前或從前向后兩兩比較相鄰元素的值朋腋，若為逆序齐疙，則交換之，直到序列比較完旭咽。
這樣一回就稱為一趟冒泡贞奋。這樣值較大的元素往下“沉”，而值較小的元素入上“浮”穷绵。
時間復(fù)雜度為O(n^2)
*/
void BubbleSort(ElemType arr[], int length)
{
int i, j;
ElemType tmp;
for (i = 0; i < length - 1; ++i)// 趟次
{
for (j = i + 1; j < length; ++j)
{
if (arr[i] > arr[j])
{
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
}
}
/*
5轿塔、快速排序算法
基本思想：基于分治法，在待排序的n個元素中任取一個元素pivot作為基準(zhǔn)，通過一趟排序?qū)⒋判虮韯澐譃楠毩⒌?br>
兩部分L[1..k-1]和L[k+1 .. n],使得第一部分中的所有元素值都小于pivot勾缭，而第二部分中的所有元素值都大于pivot揍障，
則基準(zhǔn)元素放在了其最終位置L（K）上，這個過程為一趟快速排序俩由。而后分別遞歸地對兩個子表重復(fù)上述過程毒嫡，直到每
部分內(nèi)只有一個元素或為空為止，即所有元素都放在了其最終位置上幻梯。
*/
int Partition(ElemType arr[], int left, int right)
{
ElemType pivot = arr[left]; // 以當(dāng)前表中第一個元素為樞軸值
while (left < right)
{
// 從右向左找一個比樞軸值小的元素的位置
while (left < right && arr[right] >= pivot)
{
--right;
}
arr[left] = arr[right]; // 將比樞軸值小的元素移動到左端
// 從左向右查找比樞軸值大的元素的位置
while (left < right && arr[left] <= pivot)
{
++left;
}
arr[right] = arr[left];// 將比樞軸值大的元素移動到右端
}
arr[left] = pivot; // 將樞軸元素放在最終位置
return left;
}
void QuickSort(ElemType arr[], int left, int right)
{
if (left < right)
{
int pivotPos = Partition(arr, left, right); // 劃分
QuickSort(arr, left, pivotPos - 1); // 快速排序左半部分
QuickSort(arr, pivotPos + 1, right); // 快速排序右半部分
}
}
/*
6兜畸、簡單選擇排序算法
基本思想：
假設(shè)排序表為L[1...n],第i趟排序從表中選擇關(guān)鍵字最小的元素與Li交換，第一趟排序可以確定一個元素的
最終位置碘梢，這樣經(jīng)過n-1趟排序就可以使得整個排序表有序咬摇。
*/
void SelectSort(ElemType arr[], int length)
{
int i, j, min;
ElemType tmp;
for (i = 0; i < length - 1; ++i) // 需要n-1趟
{
min = i;
for (j = i + 1; j < length; ++j)
{
if (arr[j] < arr[min]) // 每一趟選擇元素值最小的下標(biāo)
{
min = j;
}
}
if (min != i) // 如果第i趟的Li元素值該趟找到的最小元素值，則交換痘系，以使Li值最小
{
tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
}
}
/*
7菲嘴、堆排序算法
堆的定義如下：n個關(guān)鍵字序列號L[1..n]稱為堆，僅當(dāng)該序列滿足：
1）L(i) <= L(2i)且L(i) <= L(2i+1) 或 2)L(i) >= L(2i)且L(i) >= L(2i+1)
滿足第一種情況的堆汰翠，稱為小根堆（小頂堆）龄坪；
滿足第二種情況的堆，稱為大根堆（大頂堆）复唤。
*/
void HeapAdjust(ElemType *a,int i,int size) //調(diào)整堆
{
int lchild = 2 * i; //i的左孩子節(jié)點序號
int rchild = 2 * i + 1; //i的右孩子節(jié)點序號
int max = i; //臨時變量
if(i <= size / 2) //如果i是葉節(jié)點就不用進行調(diào)整
{
if (lchild <= size && a[lchild] > a[max])
{
max = lchild; // 左孩子比雙親值還大健田，需要調(diào)整
}
if (rchild <= size && a[rchild] > a[max])
{
max = rchild;// 右孩子比雙親值還大，需要調(diào)整
}
if (max != i) // 需要調(diào)整
{
ElemType tmp = a[max];
a[max] = a[i];
a[i] = tmp;
HeapAdjust(a, max, size); //避免調(diào)整之后以max為父節(jié)點的子樹不是堆
}
}
}
void BuildHeap(ElemType *a,int size) //建立堆
{
for (int i = size / 2; i >= 0; i--) //非葉節(jié)點最大序號值為size/2
{
HeapAdjust(a, i, size);
}
}
void HeapSort(ElemType *a, int size) //堆排序
{
BuildHeap(a,size);
for(int i = size - 1; i >= 0; i--)
{
swap(a[0], a[i]); //交換堆頂和最后一個元素佛纫，即每次將剩余元素中的最大者放到最后面
BuildHeap(a, i-1); //將余下元素重新建立為大頂堆
HeapAdjust(a,1,i-1); //重新調(diào)整堆頂節(jié)點成為大頂堆
}
}
void Display(ElemType arr[], int length)
{
for ( int i = 0; i < length; ++i )
{
cout << arr[i] << " ";
}
cout << endl;
}
int main()
{
ElemType arr[] = {2, 1, 5, 3, 4, 0, 6, 9, -1, 4, 12};
//InsertSort(arr, sizeof(arr) / sizeof(ElemType));
//BinaryInsertSort(arr, sizeof(arr) / sizeof(ElemType));
//ShellSort(arr, sizeof(arr) / sizeof(ElemType));
//BubbleSort(arr, sizeof(arr) / sizeof(ElemType));
//QuickSort(arr, 0, sizeof(arr) / sizeof(ElemType) - 1);
HeapSort(arr, sizeof(arr) / sizeof(ElemType));
Display(arr, sizeof(arr) / sizeof(ElemType));
return 0;
}
