排序算法讲解及代码实现
2017-05-24 本文已影响35人
豫风
共用方法
/**
交换元素位置
@param element1 元素指针
@param element2 元素指针
*/
void swapElement(int *element1 , int *element2)//交换元素位置
{
int temp = *element1;
*element1 = *element2;
*element2 = temp;
}
/**
打印数组元素
@param array 排序后的数组指针
@param count 数组长度
*/
void printArray(int *array, int count){
for (int i = 0; i<count; i++) {
NSLog(@"第%d个元素为 : %d", i, *(array + i));
}
}
1. 插入排序
思路：从数组中选中目标元素(一般从第二个元素开始)，依次和前面的数对比，边比对边移动数据元素位置，当找到合适的位置，插入目标元素。可以想象成整理麻将牌的步骤。
/**
算法 最优复杂度 最差复杂度 平均复杂度 稳定性 辅助存储
插入排序 O(n) O(n²) O(n²) 稳定 O(1)
@param array 待排序数组
@param count 数组长度
@return 排序后的数组
*/
int * insertSort(int array[], int count){
for (int i = 1; i<count; i++) {
int j;
int target = array[i];//目标元素
for (j = i; j>0 && target<array[j-1]; j--) {//结束条件
array[j] = array[j-1];//比对不合适移动元素位置
}
array[j] = target;//插入目标元素
}
return array;
}
2. shell排序
思路：shell排序是对插入排序的优化，首先对数组进行跳跃式分组，一般选择数组长度除以2（即：count/2）得到跳跃的步数，对生成的子数组进行排序。每次循环，步数/2,结束条件为步数<=1;此时的数组已经大致有序，最后使用插入排序。
/**
算法 最优复杂度 最差复杂度 平均复杂度 稳定性 辅助存储
shell排序O(n^1.3) O(n^1.3) O(n^1.3) 不稳定 O(1)
@param array 待排序数组
@param count 数组长度
@return 排序后的数组
*/
int * shellSort(int array[], int count){
int step = count / 2;
while (step>=1) { //判定结束条件
for (int i = 0; i<step; i++) {//判定走多少趟
int j = 1;
while (i + step * j < count) {//子数组的结束条件
if (array[i + step * (j-1)]>array[i + step * j]) {//交换子数组位置
swapElement(&array[i + step * (j-1)], &array[i + step * j]);
}
j++;
}
}
step = step / 2;
}
return insertSort(array, count);//调用插入排序
}
3. 选择排序
思路：假定第一个元素为最小元素，同时作为目标元素，用目标元素和后面的元素进行对比，如果大于，则记录索引，同时修改目标元素，遍历结束也就可以拿到最小值的索引，之后和起始位置的进行交换。
for循环控制流，控制跳过排序过得元素。
/**
算法 最优复杂度 最差复杂度 平均复杂度 稳定性 辅助存储
选择排序 O(n²) O(n²) O(n²) 不稳定 O(1)
@param array 待排序数组
@param count 数组长度
@return 排序后的数组
*/
int * selectSort(int array[], int count){
for (int i = 0; i < count; i++) {
int index = i;
for (int j = i; j < count-1; j++) {
if (array[j+1]<array[index]) {//设置哨兵，记录每次循环最小的。思路：默认第一个值为哨兵和后面的数以此比较，如果小于哨兵，记录索引，修改哨兵始终是最小的数，和后边的比对。最后获取到就是此次遍历的最小值，和数组中的遍历起始位置交换，从下一个位置接着下一次循环，直到跳出循环，数组排序结束，从小到大排序。
index = j+1;//记录索引
}
}
swapElement(&array[i], &array[index]);
}
return array;
}
4. 堆排序
思路：堆排序是选择排序的改进算法，不再是一步一步选择，而是根据二叉树的特性，每次筛选子二叉树。筛选完成时，将根元素和最后一个元素交换。之后迭代筛选，每次元素个数减一，直到剩余元素为一时，排序完成。
/**
算法 最优复杂度 最差复杂度 平均复杂度 稳定性 辅助存储
堆排序 O(nlogn) O(nlogn) O(nlogn) 不稳定 O(1)
@param array 待排序数组
@param count 数组长度
@return 排序后的数组
*/
int * heapSort(int array[], int count){
for (int i = count / 2; i > 0; i--) {// 构造大顶堆
heapAdjust(array, i, count);
}
for (int i = count - 1; i >= 1; i--) {
swapElement(&array[i], &array[0]); // 交换根结点与最末节点
heapAdjust(array, 0, i-1);// 剩余的n-1个元素再次建立大顶堆
}
return array;
}
void heapAdjust(int array[], int i, int count)
{
int j, temp;
temp = array[i];
j = 2 * i;
while(j <= count-1) {
if (j < count && array[j+1] > array[j]) j++; // 找出较大的子节点
if (array[j] <= temp) break; // 如果较大的子节点比父节点小, 直接返回
array[i] = array[j]; // 设置父节点为较大子节点
i = j; // 记录调整后父节点的位置
j *= 2; // 调整需要遍历的子节点
}
array[i] = temp;
}
5. 冒泡排序
思路：每次比较相邻的两个数，如果前一个数比后一个数大，交换两个数的位置，一趟遍历完成，大数已下沉到末尾，下次遍历只需要遍历到大数前一位即可，跳出循环时，已经是有序数组，从小到大。同理也可以从大到小。
/**
算法 最优复杂度 最差复杂度 平均复杂度 稳定性 辅助存储
冒泡排序 O(n) O(n²) O(n²) 稳定 O(1)
@param array 待排序数组
@param count 数组长度
@return 排序后的数组
*/
int * bubblingSort(int array[], int count){
for (int i = 0; i < count; i++) {//控制多少趟
for (int j = 0; j<count-i-1; j++) {//控制交换次数
if (array[j]>array[j+1]) {//比较相邻两个元素
swapElement(&array[j+1], &array[j]);//交换元素
}
}
}
return array;
}
6. 快速排序
思路：快速排序是冒泡排序的改进算法，采用递归分治思想。设置一个目标元素，建立左右两个索引元素，如果目标元素是第一个元素，从右边查找，同时递减右索引，直到遇到比目标元素小的值，和目标元素交换，接着和左边的元素比较，直到遇到大于目标元素，和目标元素交换。也就是目标元素依次在左右来回交换，直到左右索引相同。之后递归调用，设置一个边界条件，即可完成排序。
/**
算法 最优复杂度 最差复杂度 平均复杂度 稳定性
快速排序 O(n) O(n²) O(logn) 不稳定
@param array 待排序数组
@param left 左边界
@param right 右边界
@return 排序后的数组
*/
int * quickSort(int array[], int left, int right){
if (left>=right) {//递归结束条件
return NULL;
}
int i = left;
int j = right;
int key = array[left];
while (i<j) {//单次排序结束条件
while (i<j && array[j] >= key) {//小数向左交换条件
j--;
}
swapElement(&array[i], &array[j]);//交换元素
while (i<j && array[i] <= key) {//大数向右交换条件
i++;
}
swapElement(&array[i], &array[j]);//交换元素
}
quickSort(array, left, i - 1);//递归左分支
quickSort(array, i+1 , right);//递归右分支
return array;
}
