大家好，我是考100的代码小小顾，祝大家学习进步，加薪顺利呀。今天说一说c++选择排序算法代码_java排序代码,希望您对编程的造诣更进一步.
前言:
排序就是重新排列表中的元素，是表中的元素满足按关键字递增或递减的过程。为了查找方便，通常要求这些通常要求计算机中的，表示按关键字有序的
算法的稳定性。如果说排列表中有两个元素，A和B，它对应的关键字的话，A一定在B的前面，如果在某一序列排序算法排序以后呢，A含在B的前面，这个算法是稳定的，否则的话，这个算法是不稳定的算法是否具有稳定性，并不能衡量一个算法的优劣，他主要是对算法的性能
排序的过程中，根据元素是否完全在内存中，可将排序算法分为两类。内部排序是指在排序期间，元素全部存放在内存中的排序。外部排序是指在排序期间，元素无法全部同时存放在内存中，必须在排序的过程中，根据要求不断地在内外存之间移动的排序。一般情况下，内部排序算法在执行过程中都要进行两种操作，比较和移动，通过比较两个关键字确定对应元素的前后关系，然后通过移动元素已达到有序。当然，并非所有的内部排序算法都要基于比较操作，事实上激素排序就不给予比较，内部排序算法的性能取决于算法的时间，复杂度和空间复杂度，而时间复杂度一般是由比较和移动的次数决定的
简单选择排序
基本思想:就是在每一套里面选取后面的这些元素里面最小的一个元素。一直到最后一趟选完，只剩下最后一个元素，就不用再选了
性能分析:
空间效率:仅使用常数个辅助单元，空间效率为O(1)
时间效率:从下面的代码可以看出，在简单选择排序过程中，元素移动的操作次数很少，不会超过3(n-1)，最好的情况是移动0次，此时对应列表已经有序，但元素间比较的次数与序列的初始状态无关，所以的时间复杂度是N的平方
稳定性:在第i趟找到最小元素后，和第i个元素交换可能会导致第i个元素，与其含有相同关键字元素的相对位置发生变化。因此，简单选择排序是一种不稳定的排序方法.
代码实现
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
void printArray01(int array[], int len)
{
int i = 0;
for (i = 0; i < len; i++)
{
printf("%d", array[i]);
}
printf("\n");
}
void swap01(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
void SelectionSort(int array[], int len)
{
int i = 0;
int j = 0;
int k = -1;
for (i = 0; i < len; i++)
{
k = i;
for (j = i + 1; j < len; j++)
{
k = j;
}
swap01(array, i, k);
}
}
int main()
{
int array[] = { 12,5,34,56,77,88,666669 };
int len = sizeof(array) / sizeof(*array);
printArray01(array, len);
SelectionSort(array, len);
printArray01(array, len);
system("pause");
return 0;
}i代码100分
直接插入排序
基本思想:每次将一个待排序的记录，按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成.
空间效率:仅使用常数个辅助单元，空间效率为O(1)
时间效率:在排序过程中,向有序子表中逐个地插入元素的操作进行了N-1趟，每趟操作部分为比较关键字和移动元素，而比较次数和移动次数取决于待排序表的初始状态
稳定性:由于每次插入元素时总是向后前先比较再移动，所以不会出现相同元素相对位置发生变化的情况。直接插入排序是一个稳定的排序方法
适用性:直接插入排序算法适用于顺序存储和链式存储的线性表.为链式存储时可以从前往后查找指定元素的位置。注意，大部分排序算法都仅适用于顺序存储的线性表
代码实现
代码100分#include"stdio.h"
#include"stdlib.h"
#include"string.h"
void printArray01(int array[], int len)
{
int i = 0;
for (i = 0; i < len; i++)
{
printf("%d", array[i]);
}
printf("\n");
}
void swap01(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
void SelectionSort(int array[], int len)//这里变化了
{
int i = 0;
int j = 0;
int k = -1;
int temp = -1;
for (i = 0; i < len; i++)
{
k = i;//待插入位置
temp = array[k];
for (j =i-1;(j>0)&&(array[j] > temp);j--)
{
array[j+1] = array[j];//元素后移
k = j;//k需要插入的位置
}
array[k]=temp;
}
}
int main()
{
int array[] = { 12,5,34,56,77,88,666669 };
int len = sizeof(array) / sizeof(*array);
printArray01(array, len);
SelectionSort(array, len);
printArray01(array, len);
system("pause");
return 0;
}
冒泡排序法
基本思想:假设待排序表长为N，从后往前两两比较相应元素的值，若为逆序，则交换它们。直到序列比较完，我们把它称为冒泡
空间效率:仅使用常数个辅助单元，空间效率为O(1)
时间效率:时间复杂度是N的平方
稳定性:冒泡排序是一种稳定的排序方法
注意!!!:冒泡排序中所产生的有序子序列一定是全局有序的，不同于直接插入排序，也就是说，有序子序列中的所有元素的关键字一定小于或大于无序子序列中所有元素的关键词。这样，每趟排序都会将一个元素放置到其最终的位置上
代码实现
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
void printArray03(int array[], int len)
{
int i = 0;
for (i = 0; i < len; i++)
{
printf("%d", array[i]);
}
printf("\n");
}
void swap03(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
void SelectionSort(int array[], int len)//这里变化了
{
int i = 0;
int j = 0;
int exchange = 1;//表示数组是否已经排好序为0, 1表示没有排好序
for (i = 0; i < len&&exchange; i++)
{
exchange = 0;//认为已经排序完毕
//当置为0时,就说明已经排好了,不需要在进行下面的循环了
for (j =len-1;j>i;j--)
{
if (array[j] < array[j - 1])
{
swap03(array, j, j - 1);
exchange = 1;
//这里是冒泡的优化,假设我们之前认为这个是排好的置为0,可是后面发现没法排好就又被置位1
}
}
}
}
int main()
{
int array[] = { 12,5,34,56,77,88,666669 };
int len = sizeof(array) / sizeof(*array);
printArray03(array, len);
SelectionSort(array, len);
printArray03(array, len);
system("pause");
return 0;
}希尔排序
基本思想:是先将待排序表分割成若干形如。i,i+d,i+2d,i+3d的特殊值表分别进行直接插入排序，当整个表中的元素已成基本有序，再对全体机构进行一次直接插入排序
时间效率:由于希尔排序的时间复杂度依赖于增量序列的函数，这涉及数学上尚未解决的难题，所以其时间复杂度分析比较困难
稳定性:当相同关键字的记录被划分到不同的子表时，可能会改变它们之间的相对次序。因此，希尔排序是一种不稳定的排序方法
适用性:希尔排序算法仅适用于线性表为顺序存储的情况
代码实现
代码100分#include"stdio.h"
#include"stdlib.h"
#include"string.h"
void printArray03(int array[], int len)
{
int i = 0;
for (i = 0; i < len; i++)
{
printf("%d", array[i]);
}
printf("\n");
}
void swap03(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
void ShellSort(int array[], int len)//在插入的基础上做了一个优化,用分组的方法进行排序的
//每次都可以把问题的规模缩减三分之一
{
int i = 0;
int j = 0;
int k = 0;
int temp = -1;
int gap = len;
do
{
gap = gap / 3 + 1;
for (i = gap; i < len; i += gap)
{
k = i;
temp = array[k];
for (j = i - gap; (j >= 0) && array[j] > temp; j -= gap)
{
array[j + gap] = array[j];
k = j;
}
array[k] = temp;
}
} while (gap > 1);
}
int main()
{
int array[] = { 12,5,34,56,77,88,666669 };
int len = sizeof(array) / sizeof(*array);
printArray03(array, len);
ShellSort(array, len);
printArray03(array, len);
system("pause");
return 0;
}
快速排序法
快速排序是对冒泡排序的一种改进。
基本思想:是通过一趟排序，要将排序的数据分割成两个独立的部分，其中一部分的所有数据都比另一部分的所有数据要小。基准数据排在两个子序列的中间，然后再按此方法对这两种数据分别进行快速排序。整个排序过程可以递归进行，以此达到整个数据变成有序序列.
空间效率:由于快速排序是递归的，需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量应与递归调用的最大深度一致.
时间效率:快速排序的运行时间与划分是否对称有关，而后者由于具体使用的划分算法，有关快速排序的最坏情况发生在两个区域，分别包含N-1 个元素和0个元素，使这种最大程度的不对称性，若发生在每层递归上，对应于初始排序表基本有序或基本逆序时就得到，最坏情况下的时间复杂度为o(N的平方)
有很多方法可以提高算法的效率。一种方法，适当递归过程中划分得到的子序列的规模小时不要再继续递归调用，快速排序可以直接采用。直接插入排序算法进行后续的排序工作。另一种方法就是尽量选取一个可以将数据中分的枢轴元素，如从序列的头尾及中间选取三个元素，再取这三个元素的中间值作为最终的枢轴元素，或者随机的从当前表中选择枢轴元素。这样做可使得最坏的情况，在实际排序中几乎不会发生.
稳定性:在划分算法中，若右端区间有两个关键字相同，且均小于基准时的记录，则在交换到左端区间后，它们的相对位置会发生变化，即快速排序，也是一种不稳定的排序方法
注意，在快速排序算法中并不产生有序子序列，但每趟排序后会将一个元素放到其最终的位置上
代码实现
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
void printArray03(int array[], int len)
{
int i = 0;
for (i = 0; i < len; i++)
{
printf("%d", array[i]);
}
printf("\n");
}
void swap03(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
//划分过程 第一个元素当枢轴,分成2个有效子序列
int partition(int array[], int low, int high)
{
int pv = array[low];
while (low < high)
{
while ((low < high) && (array[high] >= pv))
{
high--;//比基准大,本来就在右边,所以要前移
}
swap03(array, low, high);
while ((low < high) && (array[high] >= pv))
{
low++;
}
swap03(array, low, high);
}
return low;//返回枢轴的位置
}
void QSort(int array[], int low, int high)
{
if (low < high)
{
//选一个pv值,把数据分别放在pv值左右两边,并把pivot位置返回出来
int pivot = partition(array, low, high);
//对子序列1排序
QSort(array,low, pivot - 1);
//对子序列2排序
QSort(array, pivot + 1, high);
}
}
void QuickSort(int array[], int len)
{
QSort(array, 0, len - 1);
}
int main()
{
//int array[] = { 12,5,34,56,77,88,666669 };
int array[] = { 11,34,56 };
int len = sizeof(array) / sizeof(*array);
printArray03(array, len);
QuickSort(array, len);
printArray03(array, len);
system("pause");
return 0;
}归并算法
归并排序与上述、基于交换选择等排序的思想不一样，规定的含义是将两个或两个以上的有序表组合成一个新的有序表
空间效率:mergr()操作中,辅助空间刚好占用N个单元，所以归并排序的空间复杂度为O(n)
时间效率:每趟归并的时间复杂度为O(n)，共需进行log2n趟归并，所以算法的时间复杂度为n(log2n)
稳定性:由于mergr()操作并不会改变相同关键字机构的相对次序。所以，2路归并排序算法是一种稳定的排序算法
代码实现
#include"stdio.h"
#include"stdlib.h"
#include"string.h"
void printArray03(int array[], int len)
{
int i = 0;
for (i = 0; i < len; i++)
{
printf("%d", array[i]);
}
printf("\n");
}
void swap03(int array[], int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
//src数组首地址 des新开辟内存空间的目的地首地址 low第一个序列最左边 mid第一个序列最右边 high第2个序列最右边
void Merge(int src[], int des[], int low, int mid, int high)
{
int i = low;
int j = mid + 1;
int k = low;
while ((i <= mid)&&(j <= high))//将小的放在目的地中
{
if (src[i] = src[j])
{
des[k++] = src[i++];
}
else
{
des[k++] = src[j++];
}
}
while (i <= mid)//若还剩几个尾部元素
{
des[k++] = src[i++];
}
while (j <= mid)//若还剩几个尾部元素
{
des[k++] = src[j++];
}
}
//每次分为2路,当只剩下一个元素的时候,就不需要在划分
void MSort(int src[], int des[], int low, int max, int high)
{
if (low == high)//只有一个元素 ,不需要归并,结果赋给des[low]
{
des[low] = src[low];
}
else//如果多个元素 进行2路划分
{
int mid = (low + high) / 2;
int *space = (int*)malloc(sizeof(int)*max);//开辟内存空间
//递归进行2路,2路的划分
//当剩下一个元素的时候,递归划分结束,然后开始merge归并操作
if (space != NULL)
{
MSort(src, space, low, mid, max);
MSort(src, space, mid+1, high, max);
MSort(space, des, low, mid, max);//调用递归函数进行归并
}
free(space);
}
}
void MergeSort(int array[], int len)
{
MSort(array, array, 0, len - 1, len);
}
int main()
{
//int array[] = { 12,5,34,56,77,88,666669 };
int array[] = { 11,34,56 };
int len = sizeof(array) / sizeof(*array);
printArray03(array, len);
MergeSort(array, len);
printArray03(array, len);
system("pause");
return 0;
}各种内部排序算法的比较和应用
前面讨论的排序算法很多，对各算法的比较也是特别重要的，一般基于三个因素进行对比。时间复杂度、空间复杂度、算法的稳定性.
算法的过程特征从时间复杂度来看，简单选择排序、直接插入排序和冒泡排序，平均情况下的时间复杂度都为o(n2)，且实现过程比较简单，但直接插入排序和冒泡排序，最好情况下的时间复杂度可以达到o(n2)。简单选择排序则与序列的初始状态无关，希尔排序作为插入排序的扩展，对较大规模的排序都可以达到很高的效率，但目前未得出精确的鉴定时间。快速排序基于分治的思想。虽然最坏情况下快速排序，时间会达到n的平方，但快速排序，平均性能可达到N乘以 log2N在实际应用中常常优于其他排序算法。归并排序同样基于分治的思想，但由于其风格子序列与初始初始序列的排序无关，因此，他的最好最坏平均时间复杂度均为n(log2n)
从空间复杂度来看，简单选择排序、插入排序、冒泡排序、希尔排序与和堆排序都仅需要介入常数个辅助空间，快速排序在空间上只使用一个小的辅助站用于实现递归，平均情况下大小为n(log2n)，当然，在最坏情况下可能会增长增长到2N2。归并排序再合并。操作中需要借助较多的辅助空间，用于元素复制大小为o(n)。虽然有方法能克服这个缺点，但其代价是算法会很复杂，且时间复杂度会增加
从稳定性看，插入排序、冒泡排序、归并排序和基数排序是稳定的排序方法，而简单选择排序、快速排序、希尔排序和堆排序都是不。稳定的排序方法对于排序方法的稳定性。应该从本身的原理上去理解，而不拘泥于死记硬背。从过程特征看，采用不同的排序方法，再一次循环或几次循环后的排序，结果可能是不同的
归纳总结
直接插入排序，冒泡排序和简单选择排序是基本的排序方法，他们主要用于元素个数不是很大的情形<=10000
对于中等规模的元素排序<=1000，希尔排序是一种很好的选择
对于元素个数N，很大的情况下可以采用快排堆排，并归并排序或激素排序，其中快排和堆排序都是不稳定的，而归并排序和基数稳定是排序是稳定的排序算法
我们可以混合使用不同的排序算法，这也是得到普遍应用的一种算法改进方法。例如，可以将直接插入排序集成到归并排序的算法中。这种混合算法能够充分发挥不同算法各自的优势，从而在整体上得到更好的性能.
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
转载请注明出处: https://daima100.com/4192.html
