C++数组排序有哪几种算法?
发布网友
发布时间：2022-05-06 02:08
共4个回答
热心网友
时间：2022-05-22 02:53
1.从有序数列和无序数列{a2,a3,…,an}开始进行排序；
2.处理第i个元素时(i=2,3,…,n) , 数列{a1,a2,…,ai-1}是已有序的,而数列{ai,ai+1,…,an}是无序的。用ai与ai-1，a i-2,…,a1进行比较,找出合适的位置将ai插入；
3.重复第二步，共进行n-1次插入处理，数列全部有序。
void insertSort(Type* arr,long len)/*InsertSort algorithm*/
{
long i=0,j=0;/*iterator value*/
Type tmpData;
assertF(arr!=NULL,"In InsertSort sort,arr is NULL\n");
for(i=1;i<len;i++)
{
j=i;
tmpData=*(arr + i);
while(j > 0 && tmpData < arr[j-1])
{
arr[j]=arr[j-1];
j--;
}
arr[j]=tmpData;
}
}
归并排序 ：归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h >
void merge(int array[], int p, int q, int r)
{
int* temp = new int [r-p+1]; //申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
int m=p;
int n=q+1;
int k = 0;
while((m<=q)&&( n<=r)) //比较两个下标所指向的元素，选择相对小的元素放入到合并空间，并移动下标到下一位置
{
if(array[m]<array[n])
{
temp[k] = array[m];
m++;
}
else
{
temp[k] = array[n];
n++;
}
k++;
}
while(m<=q) //若第一个序列有剩余，直接拷贝出来粘到合并序列尾
{
temp[k] = array[m];
k++;
m++;
}
while(n<=r) //若第二个序列有剩余，直接拷贝出来粘到合并序列尾
{
temp[k] = array[n];
k++;
n++;
}
for (int i = 0; i < (r - p +1); i++) //将排序好的序列拷贝回数组中
{
array[p+i] = temp[i];
}
}
void mergesort(int A[],int p,int r)
{
if (p<r)
{
int q = (p+r)/2;
mergesort(A,p,q);
mergesort(A,q+1,r);
merge(A,p,q,r);
}
}
int main()
{
int A[9]={9,3,6,1,4,7,2,8,5};
mergesort(A,0,8);
for (int i = 0; i < 9; i++) //打印数组
{
cout<<A[i] ;
}
return 1;
}
C# 实现归并排序
方法基本与楼上相同
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace LearnSort
{
class Program
{
static void Main(string[] args)
{
int[] arr = { 5, 4, 6, 7, 3, 5, 6, 1 };
Print(MergeSort(arr1));
}
public static int[] MergeSort(int[] arr)
{
MergeSort(arr, 0, arr.Length - 1);
return arr;
}
private static void MergeSort(int[] arr, int iStart, int iEnd)
{
if (iStart < iEnd)
{
int iMiddle = (iStart + iEnd) / 2;
MergeSort(arr, iStart, iMiddle);
MergeSort(arr, iMiddle + 1, iEnd);
MergeSort(arr, iStart, iMiddle, iEnd);
}
}
private static void MergeSort(int[] arr, int iStart, int iMiddle, int iEnd)
{
int[] temp = new int[iEnd - iStart + 1];
int m = iStart;
int n = iMiddle + 1;
int k = 0;
while (m <= iMiddle && n <= iEnd)
{
if (arr[m] < arr[n])
{
temp[k] = arr[m];
k++;
m++;
}
else
{
temp[k] = arr[n];
k++;
n++;
}
}
while (m <= iMiddle)
{
temp[k] = arr[m];
k++;
m++;
}
while (n <= iEnd)
{
temp[k] = arr[n];
k++;
n++;
}
for (k = 0, m = iStart; k < temp.Length; k++, m++)
{
arr[m] = temp[k];
}
}
public static void Print(int[] arr)
{
foreach (int i in arr)
{
System.Console.Write(i + " ");
}
System.Console.WriteLine();
}
}
}
冒泡排序：
#include <iostream>
#define LEN 9
using namespace std;
int main(){
int nArray[LEN];
for(int i=0;i<LEN;i++)nArray[i]=LEN-i;
cout<<"原始数据为："<<endl;
for(int i=0;i<LEN;i++)cout<<nArray[i]<<" ";
cout<<endl;
//开始冒泡
{
int temp;
for(int i=LEN-1;i>0;i--)
for(int j=0;j<i;j++){
if(nArray[j]>nArray[j+1]){
temp=nArray[j];
nArray[j]=nArray[j+1];
nArray[j+1]=temp;
}
}
}
//结束冒泡
cout<<"排序结果:"<<endl;
for(int i=0;i<LEN;i++)cout<<nArray[i]<<" ";
return 0;
}
快速排序：快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
源代码
#include<iostream>
using namespace std;
void QuickSort(int *pData,int left,int right)
{
int i(left),j(right),middle(0),iTemp(0);
//middle=pData[(left+right)/2];求中间值
middle=pData[(rand()%(right-left+1))+left]; //生成大于等于left小于等于right的随机数
do{
while((pData[i]<middle)&&(i<right))//从左扫描大于中值的数
i++;
while((pData[j]>middle) && (j>left))//从右扫描小于中值的数
j--;
//找到了一对值,交换
if(i<=j){
iTemp=pData[j];
pData[j]=pData[i];
pData[i]=iTemp;
i++;
j--;
}
}while(i<=j);//如果两边扫描的下标交错，就停止（完成一次）
//当左边部分有值(left<j)，递归左半边
if(left<j){
QuickSort(pData,left,j);
}
//当右边部分有值(right>i)，递归右半边
if(right>i){
QuickSort(pData,i,right);
}
}
int main()
{
int data[]={10,9,8,7,6,5,4};
const int count(6);
QuickSort(data,0,count);
for(int i(0);i!=7;++i){
cout<<data[i]<<“ ”<<flush;
}
cout<<endl;
return 0;
}
“堆”定义
n个关键字序列Kl，K2，…，Kn称为(Heap)，当且仅当该序列满足如下性质(简称为堆性质)：
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ n)
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。 （即如果按照线性存储该树，可得到一个不下降序列或不上升序列）
【例】关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示。
大根堆和小根堆：根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆，又称最小堆。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。注意：①堆中任一子树亦是堆。②以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。
堆排序
堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
（1）用大根堆排序的基本思想
① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区
② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
……
直到无序区只有一个元素为止。
（2）大根堆排序算法的基本操作：
① 初始化操作：将R[1..n]构造为初始堆；
② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。
注意：
①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。
②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止
特点
堆排序(HeapSort)是一树形选择排序。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系(参见二叉树的顺序存储结构)，在当前无序区中选择关键字最大(或最小)的记录
堆排序与直接选择排序的区别
直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果，可减少比较次数。
算法分析
堆[排序的时间，主要由建立初始]堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。
堆排序的最坏时间复杂度为O(nlog2n)。堆序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序，辅助空间为O(1)，
它是不稳定的排序方法。
[编辑本段]算法描述
堆排序算法(C++描述)
void HeapSort(SeqIAst R)
{ //对R[1..n]进行堆排序，不妨用R[0]做暂存单元
int i；
BuildHeap(R)； //将R[1-n]建成初始堆
for(i=n;i>1;i--)
{
//对当前无序区R[1..i]进行堆排序，共做n-1趟。
R[0]=R[1];
R[1]=R[i];
R[i]=R[0];//将堆顶和堆中最后一个记录交换
Heapify(R，1，i-1)；
//将R[1..i-1]重新调整为堆，仅有R[1] 可能违反堆性质
} //endfor
}
//HeapSort
因为构造初始堆必须使用到调整堆的操作，先讨论Heapify的实现，再讨论如何构造初始堆(即BuildHeap的实现)
ps：一般的数组用冒泡就好了。
热心网友
时间：2022-05-22 04:11
http://ke.baidu.com/view/58783.htm?fr=ala0_1
热心网友
时间：2022-05-22 05:45
希望能再次见面咯。
热心网友
时间：2022-05-22 07:37
http://ke.baidu.com/view/297739.htm?fr=ala0_1
http://ke.baidu.com/view/254413.htm?fr=ala0_1_1
