目录
排序的概念及其运用
排序的概念
常见的排序算法
常见排序算法的实现
插入排序
插入排序
希尔排序(缩小增量排序)
选择排序
直接选择排序
堆排序
交换排序
冒泡排序
快速排序
归并排序
非比较排序
排序算法复杂度及稳定性分析
排序的概念及其运用
排序的概念
排序:所谓排序,就是按照某个或者某些关键词的大小,按找指定顺序进行排列。
稳定性:假设在待定排序的记录序列中,经过排序之后,这些记录的相对次序保持不变,则称为这种排序算法是稳定的;否则称为不稳定。
内部排序:数据元素全部存放在内存中的排序。
外部排序:数据元素过多,无法同时存放外内存中。
常见的排序算法
常见排序算法的实现
插入排序
插入排序
插入排序:将待排序的元素按照大小逐一插入到一个已经排序好的有序队列当中,从而得到一个新的有序序列。
在生活中,扑克牌排序就运用了插入排序的思想
当插入第i(i>=0)个元素时,前面的array[0],array[1].....array[i-1]已经进行了排序,此时用array[i]的排序与前面的元素进行比较,找到array[i]的位置进行插入,原来位置上的元素向后移动。
代码实现:
//插入排序代码实现
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
{
//[0,end]为升序排列 tmp为a[end+1]元素和[0,end]元比较进行插入
//使得[0,end+1]成为升序
int end = i;
int tmp = a[end + 1];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 1] = a[end];
--end;
}
else
{
break;
}
}
a[end + 1] = tmp;
}
}
void PrintArray(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
void TestInsert()
{
int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };
InsertSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
int main(){
TestInsert();
return 0;
}
希尔排序(缩小增量排序)
希尔排序法又称缩小增量法。希尔排序的基本思想是:先选定一个整数最为距离,把待排序文件中所有记录分组,所有距离为相同的记录分为一组,并对每一组内的记录进行排序。之后缩小距离,再重复上序分组和排序工作,最后当距离为1事后,所有记录在组内完成排序。
希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。
//希尔排序代码实现
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)
{
gap = gap / 2;
//gap=gap / 3 + 1;
for (int i = 0; i < n - gap; i++)
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
void PrintArray(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
void TestShellSort()
{
int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };
ShellSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
int main(){
TestShellSort();
return 0;
}
在上述代码中 gap 取 gap / 2 ,也可取 gap / 3 +1 进行实现 ,并且时间复杂度之间,取
选择排序
直接选择排序
每一次从待排序的数据中选出最大(或最小)的一个元素,存放在序列的起始位置,直到所有待排序的元素排序完成。
//选择排序实现
//每次遍历同时找出最小值和最大值,放入队尾和队末
void SelectSort(int* a, int n)
{
int begin = 0, end = n - 1;
while (begin < end)
{
int mini = begin, maxi = begin;
for (int i = begin; i <= end; i++)
{
if (a[i] > a[maxi])
{
maxi = i;
}
if (a[i] < a[mini])
{
mini = i;
}
}
Swap(&a[begin], &a[mini]);
//如果max被换走了 则修改位置
if (maxi == begin)
{
maxi = mini;
}
Swap(&a[end], &a[maxi]);
++begin;
--end;
}
}
void PrintArray(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
void TestSelectSort()
{
int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };
ShellSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
int main(){
TestSelectSort();
return 0;
}
堆排序
堆排序(HeapSort)使用堆树数据结构所设计的一种排序算法,属于选择排序的一种。通过堆来进行数据选择。注意:排升序需要建大堆 ,排降序需要建小堆
//堆排序代码实现
void AdjustDown(int* a, int n, int parent)
{
int child = 2 * parent + 1;
while (child < n)
{
if (child + 1 < n && a[child + 1] > a[child])
{
++child;
}
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
void HeapSort(int* a, int n)
{
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(a, n, i);
}
int end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, end, 0);
--end;
}
}
void PrintArray(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
void TestHeapSort()
{
int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };
ShellSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
int main(){
TestHeapSort();
return 0;
}
交换排序
冒泡排序
冒泡排序:从序列中的第一个元素开始,依次对相邻的两个元素进行比较,如果前一个元素大于后一个元素则交换它们的位置。如果前一个元素小于或等于后一个元素,则不交换它们;直到最后一个还未排好序的元素为止。
//冒泡排序代码实现
void BubbleSort(int* a, int n)
{
for (int i = 0; i < n; i++)
{
int exchange = 0; //exchange记录是否进行交换
for (int j = 1; j < n - i; j++)
{
if (a[j - 1] > a[j])
{
Swap(&a[j], &a[j - 1]);
exchange = 1;
}
}
if (exchange == 0) //若未进行交换 则说明剩余数列均已排列
{
break;
}
}
}
void PrintArray(int* a, int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
void TestBubbleSort()
{
int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };
ShellSort(a, sizeof(a) / sizeof(int));
PrintArray(a, sizeof(a) / sizeof(int));
}
int main(){
TestBubbleSort();
return 0;
}
快速排序
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想是:任取待排序元素序列中的某元素作为基准值,按照排序码将待排序的集合分割成两个子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值。
Hoare版本
Hoare版本实现代码:
//Hoare int PartSort1(int* a, int left, int right) { int keyi = left; while (left < right) { //保证最后一个位置的数要比keyi小 要先进行--right //找比keyi小的 while (left < right && a[right] >= a[keyi]) { --right; } //找比keyi大的 while (left > right && a[left] <= a[keyi]) { ++left; } Swap(&a[left], &a[right]); } Swap(&a[keyi], &a[left]); return left; } //QickSort void QuickSort1(int* a, int begin, int end) { if (begin >= end) { return; } int keyi = PartSort1(a, begin, end); QuickSort1(a, begin, keyi - 1); QuickSort1(a, keyi + 1, end); } void PrintArray(int* a, int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } void TestQuickSort1() { int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 }; QuickSort1(a, 0, sizeof(a) / sizeof(int)-1); PrintArray(a, sizeof(a) / sizeof(int)); } int main(){ TestQuickSort1(); return 0; }
挖坑法
挖坑法代码实现:
//挖坑法 int PartSort2(int* a, int left, int right) { int key = a[left]; int hole = left; while (left < right) { while (left < right && key <= a[right]) { --right; } a[hole] = a[right]; hole = right; while (left < right && key >= a[left]) { ++left; } a[hole] = a[left]; hole = left; } a[hole] = key; return left; } //QickSort void QuickSort2(int* a, int begin, int end) { if (begin >= end) { return; } int keyi = PartSort2(a, begin, end); QuickSort2(a, begin, keyi - 1); QuickSort2(a, keyi + 1, end); } void PrintArray(int* a, int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } void TestQuickSort2() { int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 }; QuickSort2(a, 0, sizeof(a) / sizeof(int)-1); PrintArray(a, sizeof(a) / sizeof(int)); } int main(){ TestQuickSort2(); return 0; }
前后指针法
前后指针代码实现:
//前后指针法 int PartSort3(int* a, int left, int right) { int prev = left; int cur = prev + 1; int keyi = left; while (cur <= right) { if (a[cur] < a[keyi] && ++prev != cur) { Swap(&a[prev], &a[cur]); } ++cur; } Swap(&a[keyi], &a[prev]); return prev; } //QickSort void QuickSort3(int* a, int begin, int end) { if (begin >= end) { return; } int keyi = PartSort3(a, begin, end); QuickSort3(a, begin, keyi - 1); QuickSort3(a, keyi + 1, end); } void PrintArray(int* a, int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } void TestQuickSort3() { int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 }; QuickSort3(a, 0, sizeof(a) / sizeof(int)-1); PrintArray(a, sizeof(a) / sizeof(int)); } int main(){ TestQuickSort3(); return 0; }
快速排序优化
1.在上述代码中,调用了GetMidi函数,GetMidi函数可以或者数列中接近中间位置的值,从而减少递归次数。
2.在递归到小区间的时候,可以使用插入排序。
//QuickSort优化
void QuickSort4(int* a, int begin, int end)
{
if (begin > end)
{
return;
}
//小区间优化 对小区间不采用递归 使用插入排序 减少递归次数
if ((end - begin + 1) > 10)
{
int keyi = PartSort1(a, begin, end); //可以使三种方法任一钟
QuickSort4(a, begin, keyi - 1);
QuickSort4(a, keyi + 1, end);
}
else
{
InsertSort(a + begin, end - begin + 1);
}
}
非递归实现快速排序
在非递归实现快速排序时,需要调用之前的栈的实现。将每次需要排序的区间放入栈中,在获取排序区间后调用上述任一排序方法进行排序,直到所有区间 (区间大小大于0) 存入栈中并且将所有区间进行出栈获取区间后排序,此时排序完成。
//非递归实现QuickSort
void QuickSortNonR(int* a, int begin, int end)
{
ST st;
STInit(&st);
STPush(&st, end);
STPush(&st, begin);
while (!STEmpty(&st))
{
int left = STTop(&st);
STPop(&st);
int right = STTop(&st);
STPop(&st);
int keyi = PartSort1(a, left, right);
//[left,keyi-1] keyi [keyi+1,right]
if (keyi + 1 < right)
{
STPush(&st, right);
STPush(&st, keyi + 1);
}
if (left < keyi - 1)
{
STPush(&st, keyi - 1);
STPush(&st, left);
}
}
STDestroy(&st);
}
归并排序
基本思想
归并排序(Merge-Sort)建立在归并操作上的一种有效的排序算法,该算法采用分治法(Divide and Conquer)。将已有的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序。即将两个有序表合成一个有序表,称为二路归并。
递归实现
/归并排序(递归实现) void _MergeSort(int* a, int* tmp, int begin, int end) { if (end <= begin) { return; } int mid = (begin + end) / 2; _MergeSort(a, tmp, begin, mid); _MergeSort(a, tmp, mid + 1, end); int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; int index = begin; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int)); } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } _MergeSort(a, tmp, 0, n - 1); free(tmp); tmp = NULL; } void PrintArray(int* a, int n) { for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); } void TestQuickSort3() { int a[] = { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 }; MergeSort(a, 0, sizeof(a) / sizeof(int)); PrintArray(a, sizeof(a) / sizeof(int)); } int main(){ TestMergeSort(); return 0; }
非递归实现
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); exit(-1); } int gap = 1; while (gap < n) { for (int i = 0; i < n; i += 2 * gap) { int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap; //[begin1 end1] [begin2 end2] //如果第二组不存在 这两组不用进行归并 if (begin2 >= n) { break; } //如果第二组越界 ,修正边界值 if (end2 >= n) { end2 = n - 1; } int index = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } memcpy(a + i, tmp + i, (2 * gap) * sizeof(int)); } gap *= 2; } free(tmp); }
非比较排序
计数排序
计数排序:又称鸽巢原理,是对哈希直接定址发的变形应用。
主要思想:统计相同元素出现次数,根据统计的结果将序列回收到原来的序列中。
计数排序代码实现:
void CountSort(int* a, int n) { int min = a[0], max = a[0]; for(int i = 0; i < n; i++) { if (a[i] < min) { min = a[i]; } if (a[i] > max) { max = a[i]; } } //选取range 尽可能减少开辟的空间 int range = max - min + 1; int* count = (int*)malloc(sizeof(int) * range); if (count == NULL) { perror("malloc fail"); return; } memset(count, 0, sizeof(int) * range); for (int i = 0; i < n; i++) { count[a[i] - min]++; } int index = 0; for (int i = 0; i < range; i++) { while (count[i]--) { a[index++] = i + min; } } }
排序算法复杂度及稳定性分析
文章来源:https://www.toymoban.com/news/detail-839010.html
文章来源地址https://www.toymoban.com/news/detail-839010.html
到了这里,关于数据结构-常见的排序算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!