常用的各种排序算法

//常用的排序算法
#include <iostream>
using namespace std;

typedef int ElemType;

/*
1、插入排序
（1）直接插入排序算法
算法思想：将等排序列划分为有序与无序两部分，然后再依次将无序部分插入到已经有序的部分，最后

就可以形成有序序列。
操作步骤如下：
1）查找出元素L（i）在表中的插入位置K；
2）将表中的第K个元素之前的元素依次后移一个位置；
3）将L（i）复制到L（K）。

时间复杂度为：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];// 复制到“哨兵”
		
            // 将第i个元素之前的元素依次后移一个位置
			for (j = i - 1; arr[j] > guard; j--)
			{
				arr[j + 1] = arr[j];
			}

			arr[j + 1] = guard; // 复制到插入位置
		}
	}
}


/*
  2、折半插入排序
  使用于排序表为顺序存储的线性表
  在查找插入位置时，采用折半查找
  算法思想是：
  1）设置折半查找范围；
  2）折半查找
  3）移动元素
  4）插入元素
  5）继续操作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]; // 复制到哨兵
		
		// 设置折半查找范围
		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]的“特殊”子表，分别进行直接插入排序，
   当整个表已呈“基本有序”时，再对全体记录进行一次直接插入排序。
   算法过程：
   1）先取一个小于n的步长d1,把表中全部记录分成d1个组，所有距离为d1的倍数的记录放在同一组中，在各
      组中进行直接插入排序；
   2）然后取第二个步长d2 < d1, 重复步骤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、冒泡排序算法
   基本思想：
   假设待排序的表长为n， 从后向前或从前向后两两比较相邻元素的值，若为逆序，则交换之，直到序列比较完。
   这样一回就称为一趟冒泡。这样值较大的元素往下“沉”，而值较小的元素入上“浮”。
   时间复杂度为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作为基准，通过一趟排序将待排序表划分为独立的
   两部分L[1..k-1]和L[k+1 .. n],使得第一部分中的所有元素值都小于pivot，而第二部分中的所有元素值都大于pivot，
   则基准元素放在了其最终位置L（K）上，这个过程为一趟快速排序。而后分别递归地对两个子表重复上述过程，直到每
   部分内只有一个元素或为空为止，即所有元素都放在了其最终位置上。
*/

int Partition(ElemType arr[], int left, int right)
{
	ElemType pivot = arr[left]; // 以当前表中第一个元素为枢轴值

	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、简单选择排序算法
   基本思想：
   假设排序表为L[1...n],第i趟排序从表中选择关键字最小的元素与Li交换，第一趟排序可以确定一个元素的
   最终位置，这样经过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]) // 每一趟选择元素值最小的下标
			{
				min = j;
			}
		}

		if (min != i) // 如果第i趟的Li元素值该趟找到的最小元素值，则交换，以使Li值最小
		{
			tmp = arr[i];
			arr[i] = arr[min];
			arr[min] = tmp;
		}
	}
}

/*
7、堆排序算法
    堆的定义如下：n个关键字序列号L[1..n]称为堆，仅当该序列满足：
	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)  //调整堆 
{
	int lchild = 2 * i;       //i的左孩子节点序号 
	int rchild = 2 * i + 1;     //i的右孩子节点序号 
	int max = i;            //临时变量 

	if(i <= size / 2)          //如果i是叶节点就不用进行调整 
	{
		if (lchild <= size && a[lchild] > a[max])
		{
			max = lchild; // 左孩子比双亲值还大，需要调整
		}  

		if (rchild <= size && a[rchild] > a[max])
		{
			max = rchild;// 右孩子比双亲值还大，需要调整
		}

		if (max != i) // 需要调整
		{
			ElemType tmp = a[max];
			a[max] = a[i];
			a[i] = tmp;

			HeapAdjust(a, max, size);    //避免调整之后以max为父节点的子树不是堆 
		}
	}        
}

void BuildHeap(ElemType *a,int size)    //建立堆 
{
	for (int i = size / 2; i >= 0; i--)    //非叶节点最大序号值为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);      //重新调整堆顶节点成为大顶堆
	}
} 






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;
}