算法思想"/>
简单的排序算法思想
简单的排序思想
- 插入排序
- 直接插入排序
- 从前往后的直接插入排序
- 从后往前的直接插入排序(交换)
- 从后往前的直接插入排序(不交换)
- 从后往前的直接插入排序(*具有哨兵位)
- 折半插入法
- 二路插入法
- 希尔排序
- 选择排序
- 堆排序
- 冒泡排序
- 快速排序**(递归)
- 归并排序
- 基数排序(非比较排序)
- 算法效率
插入排序
直接插入排序
从前往后的直接插入排序
首先解释一下为什么传参选择left和right而不是数组元素个数n,这样做可以更加灵活的排序,比如你可以指定数组内第3个元素到第6个元素排序,而其他元素不排序
void InsertSort_1(int* ar, int left, int right)
{for (int i = left + 1; i < right; ++i){int k = left;while (ar[i] > ar[k])k++;int tmp = ar[i];for (int j = i; j > k; --j)ar[j] = ar[j - 1];ar[k] = tmp;}
}
缺点,当要排序的数字比前面排好序的数字都大时,仍然需要从头开始循环来找位置,时间效率减小。
从后往前的直接插入排序(交换)
交换函数(传址调用)
void Swap(int* a, int* b)//交换
{int tmp = *a;*a = *b;*b = tmp;
}
void InsertSort_2(int* ar, int left, int right)
{for (int i = left+1; i < right; ++i){int j = i;while (j > left && ar[j] < ar[j - 1])//j>left是为了防止越界访问{Swap(&ar[j], &ar[j - 1]);j--;}}
}
此方法有效杜绝了从前往后排序的弊端,但是会频繁调用外部交换函数,时间效率很低。
从后往前的直接插入排序(不交换)
void InsertSort_3(int* ar, int left, int right)
{for (int i = left; i < right; ++i){int j = i;int tmp = ar[j];while (j > left && tmp < ar[j - 1]){ar[j] = ar[j - 1];j--;}ar[j] = tmp;}
}
此方法有效避免使用交换函数,效率相比上面两个方法时间效率提高。
从后往前的直接插入排序(*具有哨兵位)
哨兵位设置是为了避免数组越界操作,需要多留出一个辅助空间,即省略了上述代码判断条件中“j<left”
void InsertSort_4(int* ar, int left, int right)
{for (int i = left + 1; i < right; ++i){ar[0] = ar[i];int j = i;while (ar[0] < ar[j - 1])//省略了j>left;{ar[j] = ar[j - 1];j--;}ar[j] = ar[0];}
}
需要注意的是,使用该算法时传参left在主函数中已经不是上述其他几种算法中的left,而应该是“left+1”。
折半插入法
算法思想依然是在有序的数组中查找插入位置并插入,而“查找”这一步使用二分查找法。
void BinInsertSort(int* ar, int left, int right)
{for (int i = left + 1; i < right; ++i){int tmp = ar[i];int low = left;int high = i - 1;int mid;while (low <= high){mid = (low + high) / 2;if (tmp >= ar[mid])low = mid + 1;if (tmp < ar[mid])high = mid - 1;}for (int j = i; j>low; --j){ar[j] = ar[j - 1];}ar[low] = tmp;}
}
时间效率相比上面几种方法得到了提高
二路插入法
在折半插入算法上改进优化,目的是为了减少排序过程中移动的次数,因此需要n个记录的辅助空间
void TwoWayInsertSort(int* ar, int left, int right)
{int n = right - left;int* tmp = (int *)malloc(sizeof(int)* n);tmp[0] = ar[left];int first, final;first = final = 0;for (int i = left + 1; i < right; i++){if (ar[i] < tmp[first]){first = (first - 1 + n) % n;tmp[first] = ar[i];}else if (ar[i] >= tmp[final]){tmp[++final] = ar[i];}else{int end = final;while (ar[i] < tmp[end]){tmp[(end + 1)%n] = tmp[end];//取模值是为了防止越界end = (end-1+n)%n;}tmp[(end + 1)%n] = ar[i];final++;}}int k = 0;for (int i = first; k < n; ++k)//拷贝回去{ar[k] = tmp[i];i = (i + 1) % n;}free(tmp);tmp = NULL;
}
该方法将数组访问设置成循环模式,当要插入的值为最小值时可直接插入而不需要往后挪。
希尔排序
void ShellSort(int* ar, int left, int right)
{int gap = right - left;while (gap > 1){gap = gap / 3 + 1;for (int i = left + gap; i < right; ++i){if (ar[i] < ar[i - gap]){int tmp = ar[i];int j = i;while (j>left && tmp < ar[j - gap]){ar[j] = ar[j - gap];j -= gap;}ar[j] = tmp;}}}
}
时间效率相比之前算法大幅度提高
选择排序
将第一个数看做最小的,然后通过比较将较小值与第一个数交换
int GetMinIndex(int* ar, int left, int right)//获取最小下标
{int min_value = ar[left];int index = left;for (int i = left + 1; i < right; ++i){if (ar[i] < min_value){min_value = ar[i];index = i;}}return index;
}void SelectSort(int* ar, int left, int right)
{for (int i = left; i < right - 1; ++i){int index = GetMinIndex(ar, i, right);if (index != i)Swap(&ar[i], &ar[index]);}
}
是一种比较中庸的排序算法
堆排序
升序大堆,降序小堆
void AdjustDown(int* ar, int left, int right, int start)//赋值法向下调整
{int n = right - left;int i = start;int j = 2*i + 1;int tmp = ar[i];while (j < n){if (j + 1 < n && ar[j] < ar[j + 1])//右树存在且左树大于右数j = j + 1;if (tmp < ar[j]){ar[i] = ar[j];//满足条件向上赋值i = j;j = i * 2 + 1;}elsebreak;}ar[i] = tmp;
}void HeapSort(int* ar, int left, int right)
{int n = right - left;int curpos = n / 2 - 1 + left;//找到最后一个分支while (curpos >= 0){AdjustDown(ar, left, right, curpos);curpos--;}//将顶与低交换int end = right - 1;while (end > left){Swap(&ar[left], &ar[end]);//出堆AdjustDown(ar, left, end, 0);end--;}
}
堆排序的算法思想基于二叉树遍历,所以时间效率很高
冒泡排序
一种比较入门的排序思路,时间效率最低。
void BubbleSort_1(int* ar, int left, int right)
{bool flag = false;for (int i = left; i < right - left - 1; ++i){for (int j = left; j < right - left - 1 - i; ++j){if (ar[j] > ar[j + 1]){Swap(&ar[j], &ar[j + 1]);flag = true;}}if (!flag)break;elseflag = false;}
}
加上flag可避免不必要的比较
快速排序**(递归)
在这里写出三种算法取左右序列分界点的下标:
int _Partition_1(int* ar, int left, int right)//hoare法
{int low = left, high = right - 1;int key = ar[low];while (low < high){while (low < high && ar[high] > key)high--;Swap(&ar[low], &ar[high]);while (low < high && ar[low] <= key)low++;Swap(&ar[low], &ar[high]);}return low;
}int _Partition_2(int* ar, int left, int right)//挖坑法
{int low = left, high = right - 1;int key = ar[low];while (low < high){while (low < high && ar[high] > key)high--;ar[low] = ar[high];while (low < high && ar[low] <= key)low++;ar[high] = ar[low];}ar[low] = key;return low;
}int _Partition_3(int* ar, int left, int right)//前后指针法
{int key = ar[left];int pos = left;for (int i = pos + 1; i < right; ++i){if (ar[i] < key){pos++;if (pos != i){Swap(&ar[pos], &ar[i]);}}}Swap(&ar[left], &ar[pos]);return pos;
}void QuickSort(int* ar, int left, int right)
{if (left >= right)return;int pos = _Partition_3(ar, left, right);QuickSort(ar, left, pos);//左子序列QuickSort(ar, pos + 1, right);//右子序列
}
最常用的高效排序算法
归并排序
归并排序算法思想:将n个记录看成n个子序列,每个子序列长度为1,两两归并得到长度为2的有序子序列,循环进行,直到长度为n
void _MergeSort(int* ar, int left, int right,int* tmp)
{if (left >= right)return;int mid = (left + right) / 2;_MergeSort(ar, left, mid, tmp);//分解左边分支_MergeSort(ar, mid + 1, right, tmp);//分解右边分支归并int begin1, end1, begin2, end2;begin1 = left, end1 = mid;begin2 = mid + 1, end2 = right;int k = left;while (begin1 <= end1 && begin2 <= end2){if (ar[begin1] < ar[begin2])tmp[k++] = ar[begin1++];elsetmp[k++] = ar[begin2++];}while (begin1 <= end1)tmp[k++] = ar[begin1++];while (begin2 <= end2)tmp[k++] = ar[begin2++];memcpy(ar + left, tmp + left, sizeof(int)* (right - left + 1));}void MergeSort(int* ar, int left, int right)
{int n = right - left;int * tmp = (int*)malloc(sizeof(int)* n);_MergeSort(ar, left, right-1,tmp);free(tmp);
}
稳定排序且效率高
基数排序(非比较排序)
又称多关键字排序,这边给出算法思想:
算法效率
void TestSortEfficient()
{int n = 20000;int* a = (int*)malloc(sizeof(int)*n);int* a1 = (int*)malloc(sizeof(int)*n);int* a2 = (int*)malloc(sizeof(int)*n);int* a3 = (int*)malloc(sizeof(int)*n);int* a4 = (int*)malloc(sizeof(int)*n);int* a5 = (int*)malloc(sizeof(int)*n);int* a6 = (int*)malloc(sizeof(int)*n);int* a7 = (int*)malloc(sizeof(int)*n);int* a8 = (int*)malloc(sizeof(int)*n);int* a9 = (int*)malloc(sizeof(int)*n);int* a10 = (int*)malloc(sizeof(int)*n);int* a11 = (int*)malloc(sizeof(int)*n);int* a12 = (int*)malloc(sizeof(int)*n);int* a13 = (int*)malloc(sizeof(int)*n);int* a14 = (int*)malloc(sizeof(int)*n);srand(time(0));for (int i = 0; i < n; ++i){a[i] = rand();a1[i] = a[i];a2[i] = a[i];a3[i] = a[i];a4[i] = a[i];a5[i] = a[i];a6[i] = a[i];a7[i] = a[i];a8[i] = a[i];a9[i] = a[i];a10[i] = a[i];a11[i] = a[i];a12[i] = a[i];a13[i] = a[i];a14[i] = a[i];}time_t start = clock();InsertSort_1(a, 0, n);time_t end = clock();printf("InsertSort_1 time = %u\n", end - start);start = clock();InsertSort_2(a1, 0, n);end = clock();printf("InsertSort_2 time = %u\n", end - start);start = clock();InsertSort_3(a2, 0, n);end = clock();printf("InsertSort_3 time = %u\n", end - start);start = clock();InsertSort_4(a3, 0, n);end = clock();printf("InsertSort_4 time = %u\n", end - start);start = clock();BinInsertSort(a4, 0, n);end = clock();printf("BinInsertSort time = %u\n", end - start);start = clock();TwoWayInsertSort(a5, 0, n);end = clock();printf("TwoWayInsertSort time = %u\n", end - start);start = clock();ShellSort(a6, 0, n);end = clock();printf("ShellSort time = %u\n", end - start);start = clock();SelectSort(a7, 0, n);end = clock();printf("SelectSort time = %u\n", end - start);start = clock();HeapSort(a8, 0, n);end = clock();printf("HeapSort time = %u\n", end - start);start = clock();BubbleSort(a9, 0, n);end = clock();printf("BubbleSort time = %u\n", end - start);start = clock();BubbleSort_1(a10, 0, n);end = clock();printf("BubbleSort_1 time = %u\n", end - start);start = clock();QuickSort(a11, 0, n);end = clock();printf("QuickSort time = %u\n", end - start);start = clock();QuickSort_1(a12, 0, n);end = clock();printf("QuickSort_1 time = %u\n", end - start);start = clock();MergeSort(a13, 0, n);end = clock();printf("MergeSort time = %u\n", end - start);start = clock();RadixSort(a14, 0, n);end = clock();printf("RadixSort time = %u\n", end - start);
}
得出结果
时间效率如下:
标没有十全十美的排序算法,有优点就有缺点,快速排序性能优越但是不稳定,需要辅助空间,对于少量的数据排序效率不高
更多推荐
简单的排序算法思想
发布评论