算法设计排序算法

Ⅰ java:设计一个通用的排序算法.

import java.util.Arrays;
class Stu implements Comparable{
String name;
int id;

public Stu (String n, int i){
name = n;
id = i;
}

public int compareTo(Object o){
Stu m = (Stu) o;
if (id > m.id){
return 1;
} else if(id < m.id){
return -1;
} else return 0;
}

public String toString(){
return "("+name+","+id+")";
}

}

class Rec implements Comparable{
int c, k;
public Rec (int m, int n){
c = m;
k = n;
}

int area (){
return c*k;
}

public int compareTo(Object o){
Rec m = (Rec) o;
if (this.area() > m.area()){
return 1;
} else if(this.area() < m.area()) {
return -1;
}else return 0;
}

public String toString(){
return "(" + "边长为" + c + "和" + k + "面积为" + this.area() + ")";
}
}

public class TestSort {
public static void main (String [] args){
Stu [] a = new Stu [5];
a[0] = new Stu("ZhangSan",6);
a[1] = new Stu("LiSi",3);
a[2] = new Stu("WangWu",9);
a[3] = new Stu("ZhaoLiu",12);
a[4] = new Stu("QianQi",4);
sort (a);
for (int i=0; i<a.length; i++){
System.out.println("name="+ a[i].name + " " + "id=" + a[i].id);
}

Rec[] b = {new Rec(4,5), new Rec(7,2), new Rec(8,3), new Rec(2,11), new Rec(5,5)};

System.out.println();
Arrays.sort(a); //此为调用Arrays.sort()方法自动排序;
System.out.println("排序后"+Arrays.toString(a));
Arrays.sort(b);
System.out.println("排序后"+Arrays.toString(b));
}
/*下面为用冒泡排序法排序;本人学艺不精，有一点小问题，编译时可以通过，但是不起作用。主要是定义Comparable对象c来传递o对象的值时出现传递不成功的现象。
static void sort (Comparable[] o){
int m = o.length-1;
for(int i=m; i>1; i--){
for(int j=0; j<i; j++){
if(o[j].compareTo(o[j+1])>1){
Comparable c =(Comparable) o[j];
o[j] = o[j+1];
o[j+1] = c;
}
}
}
}*/
}

Ⅱ 排序算法课程设计

// 各种排序算法汇总.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
#include <string>
using namespace std;

#include <stack>
#include <time.h>
#include <stdlib.h>

template < typename T >
class SqList
{
private:
int length;
T * r;
public://接口
SqList(int n = 0);//构造长度为n的数组
~SqList()
{
length = 0;
delete r;
r = NULL;
}
void InsertSort();//顺序插入排序
void DisPlay();//输出元素
void BInsertSort();//折半插入排序
void ShellSort(int dlta[],int t);//希尔排序
void QuickSort();//快速排序
void SelectSort();//简单选择排序
void BubbleSort();//改进冒泡排序
void Bubble_Sort2();//相邻两趟是反方向起泡的冒泡排序算法
void Bubble_Sort3();//对相邻两趟反方向算法进行化简,循环体中只包含一次冒泡
void HeapSort();//堆排序
void Build_Heap_Sort();//堆排序由小到大序号建立大根堆
void MergeSort();//归并排序
void OE_Sort();//奇偶交换排序的算法

void Q_Sort_NotRecurre();//非递归快速排序
void HeapSort_3();//三叉堆排序

public://调用
void ShellInsert(int dk);//一趟希尔排序
void QSort(int low,int high);//快速排序
int Partition(int low,int high);//一趟快速排序
int SelectMinKey(int i);//从i到length中选择最小值下标
void HeapAdjust(int s,int m);//调整s的位置,其中s+1~m有序
void HeapAdjust_3(int s,int m);//三叉堆****调整s的位置,其中s+1~m有序
void Merge(T SR[],T TR[],int i,int m,int n);//归并
void MSort(T SR[],T TR1[],int s,int t);//归并
void Easy_Sort(int low,int high);//3个数直接排序
void Build_Heap(int len);//从低下标到高下标逐个插入建堆的算法***建立大根堆**但为排序

};
template < typename T >
SqList<T>::SqList(int n = 0)
{
//srand( time(0) );
length = n;
r=new T[length+1];
T t;
cout<<"随机生成"<<n<<"个值:"<<endl;
for (int i=1;i<=length;i++)
{
//cin>>t;
r[i] = rand()%1000;
//r[i] = t;
}
for (int i=1; i<=length;i++)
cout<<r[i]<<",";
cout<<endl;
}
template < typename T >
void SqList<T>::InsertSort()
{
int i,j;
for (i=2;i<=length;i++)
{
if (r[i]<r[i-1])
{
r[0]=r[i];
r[i]=r[i-1];
for (j=i-2;r[0]<r[i-2];j--)
r[j+1]=r[j];
r[j+1]=r[0];
}
}
}
template < typename T >
void SqList<T>::DisPlay()
{
int i;
cout<<length<<" 元素为："<<endl;
for (i = 1;i < length+1;i++ )
{
cout<<r[i]<<" ,";
}
cout<<endl;
}
template < typename T >
void SqList<T>::BInsertSort()
{
int i, j, m;
int low,high;
for (i = 2;i<= length;i++)
{
r[0]=r[i];
low=1;
high=i-1;
while (low<=high)
{
m = (low+high)/2;
if ( r[0] < r[m] )
high=m-1;
else
low=m+1;
}
for ( j=i-1;j >=high+1; j--)
{
r[j+1] = r[j];
}
r[high+1] = r[0];
}
}

template < typename T >
void SqList<T>::ShellInsert(int dk)
{
int i,j;
for (i=dk+1;i<=length;i++)
if (r[i] < r[i-dk])
{
r[0] = r[i];
for ( j=i-dk; j>0 && r[0] < r[j]; j-=dk)
{
r[j+dk]=r[j];
}
r[j+dk] = r[0];
}
}
template < typename T >
void SqList<T>::ShellSort(int dlta[],int t)
{
int k=0;
for (;k<t;k++)
{
ShellInsert(dlta[k]);
}
}
template < typename T >
int SqList<T>::Partition(int low,int high)
{
int pivotkey;
r[0] = r[low];//记录枢轴值
pivotkey = r[low];
while (low < high)
{
while (low < high&& r[high] >= pivotkey)
high--;
r[low] = r[high];
while (low < high&& r[low] <= pivotkey)
low++;
r[high] = r[low];
}
r[low] = r[0];//枢轴记录到位
return low;//返回枢轴位置
}
template < typename T >
void SqList<T>::QSort(int low,int high)
{
int pivotloc;
if (low < high)
{
pivotloc = Partition(low,high);
QSort(low,pivotloc-1);
QSort(pivotloc+1,high);
}
}
template < typename T >
void SqList<T>::QuickSort()
{
QSort(1,length);
}
template < typename T >
int SqList<T>::SelectMinKey(int i)
{
int j,min=i;
for (j=i;j <= length;j++)
{
if (r[min] > r[j])
{
min = j;
}
}
return min;
}
template < typename T >
void SqList<T>::SelectSort()
{
int i,j;
T t;
for (i=1;i < length;i++)//循环length-1次不是length次
{
j=SelectMinKey(i);
if (i != j)
{
t= r[j];
r[j]=r[i];
r[i]=t;
}
}
}
template < typename T >
void SqList<T>::BubbleSort()
{
int i,j;
int flag=1;//标识位，如果出现0，则没有交换，立即停止
T t;
for (i=1;i < length && flag;i++)
{
flag = 0;
for (j=length-1;j>=i;j--)
if (r[j]>r[j+1])
{
t=r[j];
r[j]=r[j+1];
r[j+1]=t;
flag=1;
}
}
}
template < typename T >
void SqList<T>::Bubble_Sort2()
{
bool change = true;
int low = 1, high = length;
int i;
T t;
while ( (low < high) && change )
{
change = false;
for ( i = low; i < high; i++ )
{
if ( r[i] > r[i+1] )
{
t = r[i];
r[i] = r[i+1];
r[i+1] = t;
change = true;
}
}
high-=1;
for ( i = high; i > low; i-- )
{
if ( r[i] < r[i-1] )
{
t = r[i];
r[i] = r[i-1];
r[i-1] = t;
change = true;
}
}
low+=1;
}
}

template < typename T >
void SqList<T>::Bubble_Sort3()
{
int i,d=1;
bool change = true;
int b[3] = {1,0,length};//b[0]为冒泡的下界,b[ 2 ]为上界,b[1]无用
T t;
while (change)//如果一趟无交换，则停止
{
change = false;
for ( i=b[1-d]; i!=b[1+d]; i=i+d )//统一的冒泡算法
{
if ( (r[i]-r[i+d])*d > 0 )///注意这个交换条件
{
t = r[i];
r[i] = r[i+d];
r[i+d] = t;
change = true;
}
}
d = d*(-1);//换个方向
}
}
template < typename T >
void SqList<T>::HeapAdjust(int s,int m)
{
/* 已知H.r[s..m]中记录的关键字除H.r[s].key之外均满足堆的定义，本函数 */
/* 调整H.r[s]的关键字,使H.r[s..m]成为一个大顶堆(对其中记录的关键字而言) */
int j;
T rc = r[s];
for (j=2*s;j <= m;j*=2)
{
/* 沿key较大的孩子结点向下筛选 */
if (j < m && r[j] < r[j+1])
j++;/* j为key较大的记录的下标 */
if (rc >= r[j])
break;/* rc应插入在位置s上 ,无需移动*/
r[s]=r[j];
s=j;
}
r[s]=rc;/* 插入 */
}
template < typename T >
void SqList<T>::HeapSort()
{
/* 对顺序表H进行堆排序。算法10.11 */
T t;
int i;
for (i=length/2;i>0;i--)/* 把H.r[1..H.length]建成大顶堆 */
HeapAdjust(i,length);
for (i=length;i>1;i--)
{
/* 将堆顶记录和当前未经排序子序列H.r[1..i]中最后一个记录相互交换 */
t=r[1];
r[1]=r[i];
r[i]=t;
HeapAdjust(1,i-1);/* 将H.r[1..i-1]重新调整为大顶堆 */
}
}
template < typename T >
void SqList<T>::Build_Heap_Sort()
{
int i;
Build_Heap(length);
for ( i = length; i > 1; i-- )
{
T t;
t = r[i];
r[i] = r[1];
r[1] = t;
Build_Heap(i-1);
}

}
template < typename T >
void SqList<T>::Build_Heap(int len)
{
T t;
for (int i=2; i <= len; i++ )
{
int j = i;
while ( j != 1 )
{
int k = j/2;
if ( r[j] > r[k] )
{
t = r[j];
r[j] = r[k];
r[k] = t;
}
j = k;
}
}

}
template < typename T >
void SqList<T>::Merge(T SR[],T TR[],int i,int m,int n)
{
/* 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n] 算法10.12 */
int j,k,x;
for (j=m+1,k=i;j<=n&&i<=m;k++)/* 将SR中记录由小到大地并入TR */
{
if (SR[i]<SR[j])
TR[k]=SR[i++];
else
TR[k]=SR[j++];
}
if (i<=m)
for (x=0;x<=m-i;x++)
TR[k+x]=SR[i+x];/* 将剩余的SR[i..m]复制到TR */
if (j<=n)
for (x=0;x<=n-j;x++)
TR[k+x]=SR[j+x];/* 将剩余的SR[j..n]复制到TR */
}
template < typename T >
void SqList<T>::MSort(T SR[],T TR1[],int s,int t)
{
/* 将SR[s..t]归并排序为TR1[s..t]。算法10.13 */
int m;
T *TR2=new T[length+1];
if (s==t)
TR1[s]=SR[s];
else
{
m=(s+t)/2;/* 将SR[s..t]平分为SR[s..m]和SR[m+1..t] */
MSort(SR,TR2,s,m);/* 递归地将SR[s..m]归并为有序的TR2[s..m] */
MSort(SR,TR2,m+1,t);/* 递归地将SR[m+1..t]归并为有序的TR2[m+1..t] */
Merge(TR2,TR1,s,m,t);/* 将TR2[s..m]和TR2[m+1..t]归并到TR1[s..t] */
}
}
template < typename T >
void SqList<T>::MergeSort()
{
MSort(r,r,1,length);
}
template < typename T >
void SqList<T>::OE_Sort()
{
int i;
T t;
bool change = true;
while ( change )
{
change = false;
for ( i=1;i<length;i+=2 )
{
if (r[i] > r[i+1])
{
t = r[i];
r[i] = r[i+1];
r[i+1] = t;
change = true;
}
}
for ( i=2;i<length;i+=2 )
{
if ( r[i] > r[i+1] )
{
t = r[i];
r[i] = r[i+1];
r[i+1] = t;
change = true;
}
}

}

}
typedef struct
{
int low;
int high;
}boundary;
template <typename T >
void SqList<T>::Q_Sort_NotRecurre()
{
int low=1,high=length;
int piv;
boundary bo1,bo2;
stack<boundary> st;
while (low < high)
{
piv = Partition(low,high);
if ( (piv-low < high-piv) && (high-piv > 2) )
{
bo1.low = piv+1;
bo1.high = high;
st.push(bo1);
high = piv-1;
}
else if ( (piv-low > high-piv) && (piv-low >2) )
{
bo1.low = low;
bo1.high = piv-1;
st.push(bo1);
low = piv+1;
}
else
{
Easy_Sort(low,high);
high = low;
}
}
while ( !st.empty() )
{
bo2 = st.top();
st.pop();
low = bo2.low;
high = bo2.high;
piv = Partition(low, high);
if ( (piv-low < high-piv) && (high-piv > 2) )
{
bo1.low = piv+1;
bo1.high = high;
st.push(bo1);
high = piv-1;
}
else if ( (piv-low > high-piv) && (piv-low >2) )
{
bo1.low = low;
bo1.high = piv-1;
st.push(bo1);
low = piv+1;
}
else
{
Easy_Sort(low,high);
}
}

}
template < typename T >
void SqList<T>::Easy_Sort(int low,int high)
{
T t;
if ( (high-low) == 1 )
{
if ( r[low] > r[high] )
{
t = r[low];
r[low] = r[high];
r[high] = t;
}
}
else
{
if ( r[low] > r[low+1] )
{
t = r[low];
r[low] = r[low+1];
r[low+1] = t;
}
if ( r[low+1] > r[high] )
{
t = r[low+1];
r[low+1] = r[high];
r[high] = t;
}
if ( r[low] > r[low+1] )
{
t = r[low];
r[low] = r[low+1];
r[low+1] = t;
}
}

}

template < typename T >
void SqList<T>::HeapAdjust_3(int s,int m)
{
T rc = r[s];
for (int j = 3*s-1; j <= m;j=j*3-1)
{
if (j+1<m)//有3个孩子结点
{
if ( rc>=r[j] && rc>=r[j+1] && rc>=r[j+2] )
break;
else
{
if ( r[j] > r[j+1] )
{
if ( r[j] > r[j+2] )
{
r[s]=r[j];
s=j;
}
else//r[j]<=r[j+2]
{
r[s]=r[j+2];
s=j+2;
}
}
else//r[j]<=r[j+1]
{
if ( r[j+1] > r[j+2] )
{
r[s]=r[j+1];
s=j+1;
}
else//r[j+1]<=r[j+2]
{
r[s]=r[j+2];
s=j+2;
}
}
}
}
if ( j+1==m )//有2个孩子结点
{
if ( rc>=r[j] && rc>=r[j+1] )
break;
else
{
if ( r[j] > r[j+1] )
{
r[s]=r[j];
s=j;
}
else//r[j]<=r[j+1]
{
r[s]=r[j+1];
s=j+1;
}
}
}
if (j==m)//有1个孩子结点
{
if ( rc>=r[j] )
break;
else
{
r[s]=r[j];
s=j;
}
}
}
r[s]=rc;
}

template <typename T >
void SqList<T>::HeapSort_3()
{
int i;
T t;
for (i=length/3; i>0; i--)
HeapAdjust_3(i,length);
for ( i=length; i > 1; i-- )
{
t = r[i];
r[i] = r[1];
r[1] = t;
HeapAdjust_3(1,i-1);
}
}

int _tmain(int argc, _TCHAR* argv[])
{
SqList<int> Sq(15);
//Sq.InsertSort();
//Sq.BInsertSort();
/* 希尔排序*/
// int a[5]={5,4,3,2,1};
// Sq.ShellSort(a,5);

/* Sq.QuickSort();*/

// Sq.SelectSort();

/* Sq.BubbleSort();*/

/* Sq.HeapSort();*/

/* Sq.MergeSort();*/

/* Sq.Q_Sort_NotRecurre();*/

/* Sq.Bubble_Sort2();*/
/* Sq.OE_Sort();*/
/* Sq.Bubble_Sort3();*/

/* Sq.Build_Heap_Sort();*/

Sq.HeapSort_3();

Sq.DisPlay();
system("pause");
return 1;
}

Ⅲ 排序算法设计

到底用什么语言编啊？我会用Java和C++，不过代码一时没有，我会尽快给你的～～～～～

Ⅳ 程序设计中有哪些排序算法用C语言分别怎样实现

开始学的是冒泡排序。
冒泡的思想比较简单，就是比较相邻两数的大小。将大的后移动，这样第一次的结果最大的数就在最后了。然后再从第一个数开始比较。接下来就是同样的处理了。
然后就快排比较实用了。快排没必要用一次写一次，可以直接调用函数。
在调用函数的是时候注意比较函数的写法 可以实现多种数据的排序。很适合结构体排序。
思想是将你要排序的东西分成多个相似的模块进行递归处理。
比如：在R[low..high]中任选一个记录作为基准(Pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1)和R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置(pivotpos)上，它无须参加后续的排序。

Ⅳ JS常见排序算法

排序算法说明:

（1）对于评述算法优劣术语的说明

稳定 ：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；

不稳定 ：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面；

内排序 ：所有排序操作都在内存中完成；

外排序 ：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

时间复杂度 : 一个算法执行所耗费的时间。

空间复杂度 : 运行完一个程序所需内存的大小。

(2)排序算法图片总结:

1.冒泡排序:

解析：1.比较相邻的两个元素，如果前一个比后一个大，则交换位置。

2.第一轮的时候最后一个元素应该是最大的一个。

3.按照步骤一的方法进行相邻两个元素的比较，这个时候由于最后一个元素已经是最大的了，所以最后一个元素不用比较。

2.快速排序:

解析：快速排序是对冒泡排序的一种改进，第一趟排序时将数据分成两部分，一部分比另一部分的所有数据都要小。然后递归调用，在两边都实行快速排序。

3.插入排序:

解析：

 （1） 从第一个元素开始，该元素可以认为已经被排序

 （2） 取出下一个元素，在已经排序的元素序列中从后向前扫描

 （3） 如果该元素（已排序）大于新元素，将该元素移到下一位置

 （4） 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

 （5）将新元素插入到下一位置中

 （6） 重复步骤2

2.二分查找:

解析：二分查找，也为折半查找。首先要找到一个中间值，通过与中间值比较，大的放又，小的放在左边。再在两边中寻找中间值，持续以上操作，直到找到所在位置为止。

（1）递归方法

（2）非递归方法

4.选择排序:

解析:首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。

以此类推，直到所有元素均排序完毕。

5.希尔排序:

解析:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序

6.归并排序:

解析:归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

7.堆排序:

解析:堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是

小于（或者大于）它的父节点。

8.计数排序:

 解析:计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

9.桶排序:

解析:假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排

10.基数排序:

解析:基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优

先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。

基数排序 vs 计数排序 vs 桶排序

这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：

基数排序：根据键值的每位数字来分配桶 计数排序：每个桶只存储单一键值 桶排序：每个桶存储一定范围的数值

Ⅵ 面试必会八大排序算法（Python）

一、插入排序

介绍

插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。

算法适用于少量数据的排序，时间复杂度为O(n^2)。

插入排算法是稳定的排序方法。

步骤

①从第一个元素开始，该元素可以认为已经被排序

②取出下一个元素，在已经排序的元素序列中从后向前扫描

③如果该元素（已排序）大于新元素，将该元素移到下一位置

④重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

⑤将新元素插入到该位置中

⑥重复步骤2

排序演示

算法实现

二、冒泡排序

介绍

冒泡排序（Bubble Sort）是一种简单的排序算法，时间复杂度为O(n^2)。

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

原理

循环遍历列表，每次循环找出循环最大的元素排在后面；

需要使用嵌套循环实现：外层循环控制总循环次数，内层循环负责每轮的循环比较。

步骤

①比较相邻的元素。如果第一个比第二个大，就交换他们两个。

②对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

③针对所有的元素重复以上的步骤，除了最后一个。

④持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

算法实现：

三、快速排序

介绍

快速排序（Quicksort）是对冒泡排序的一种改进，借用了分治的思想，由C. A. R. Hoare在1962年提出。

基本思想

快速排序的基本思想是：挖坑填数 + 分治法。

首先选出一个轴值(pivot，也有叫基准的)，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

实现步骤

①从数列中挑出一个元素，称为 “基准”（pivot）；

②重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）；

③对所有两个小数列重复第二步，直至各区间只有一个数。

排序演示

算法实现

四、希尔排序

介绍

希尔排序（Shell Sort）是插入排序的一种，也是缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法，时间复杂度为：O(1.3n)。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

·插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率；

·但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位。

基本思想

①希尔排序是把记录按下标的一定量分组，对每组使用直接插入算法排序；

②随着增量逐渐减少，每组包1含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法被终止。

排序演示

算法实现

五、选择排序

介绍

选择排序(Selection sort)是一种简单直观的排序算法，时间复杂度为Ο(n2)。

基本思想

选择排序的基本思想：比较 + 交换。

第一趟，在待排序记录r1 ~ r[n]中选出最小的记录，将它与r1交换；

第二趟，在待排序记录r2 ~ r[n]中选出最小的记录，将它与r2交换；

以此类推，第 i 趟，在待排序记录ri ~ r[n]中选出最小的记录，将它与r[i]交换,使有序序列不断增长直到全部排序完毕。

排序演示

选择排序的示例动画。红色表示当前最小值，黄色表示已排序序列，蓝色表示当前位置。

算法实现

六、堆排序

介绍

堆排序（Heapsort）是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。

利用数组的特点快速指定索引的元素。

基本思想

堆分为大根堆和小根堆，是完全二叉树。

大根堆的要求是每个节点的值不大于其父节点的值，即A[PARENT[i]] >=A[i]。

在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

排序演示

算法实现

七、归并排序

介绍

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

基本思想

归并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

算法思想

自上而下递归法（假如序列共有n个元素）

① 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；

② 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；

③ 重复步骤②，直到所有元素排序完毕。

自下而上迭代法

① 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

② 设定两个指针，最初位置分别为两个已经排序序列的起始位置；

③ 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

④ 重复步骤③直到某一指针达到序列尾；

⑤ 将另一序列剩下的所有元素直接复制到合并序列尾。

排序演示

算法实现

八、基数排序

介绍

基数排序（Radix Sort）属于“分配式排序”，又称为“桶子法”。

基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m) ，其中 r 为采取的基数，而m为堆数。

在某些时候，基数排序法的效率高于其他的稳定性排序法。

基本思想

将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

基数排序按照优先从高位或低位来排序有两种实现方案：

MSD（Most significant digital） 从最左侧高位开始进行排序。先按k1排序分组, 同一组中记录, 关键码k1相等,再对各组按k2排序分成子组, 之后, 对后面的关键码继续这样的排序分组, 直到按最次位关键码kd对各子组排序后. 再将各组连接起来,便得到一个有序序列。MSD方式适用于位数多的序列。

LSD （Least significant digital）从最右侧低位开始进行排序。先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。LSD方式适用于位数少的序列。

排序效果

算法实现

九、总结

各种排序的稳定性、时间复杂度、空间复杂度的总结：

平方阶O(n²)排序：各类简单排序：直接插入、直接选择和冒泡排序；

从时间复杂度来说：

线性对数阶O(nlog₂n)排序：快速排序、堆排序和归并排序；

O(n1+§))排序，§是介于0和1之间的常数：希尔排序 ；

线性阶O(n)排序：基数排序，此外还有桶、箱排序。

Ⅶ 算法设计快速排序完整程序

#include
<stdio.h>
#define
MAX
255
int
R[MAX];
int
Partition(int
i,int
j)
{/*
调用Partition(R，low，high)时，对R[low..high]做划分，*/
/*
并返回基准记录的位置
*/
int
pivot=R[i];
/*
用区间的第1个记录作为基准
*/
while(i<j){
/*
从区间两端交替向中间扫描，直至i=j为止
*/
while(i<j&&R[j]>=pivot)
/*
pivot相当于在位置i上
*/
j--;
/*
从右向左扫描，查找第1个关键字小于pivot.key的记录R[j]
*/
if(i<j)
/*
表示找到的R[j]的关键字<pivot.key
*/
R[i++]=R[j];
/*
相当于交换R[i]和R[j]，交换后i指针加1
*/
while(i<j&&R[i]<=pivot)
/*
pivot相当于在位置j上*/
i++;
/*
从左向右扫描，查找第1个关键字大于pivot.key的记录R[i]
*/
if(i<j)
/*
表示找到了R[i]，使R[i].key>pivot.key
*/
R[j--]=R[i];
/*
相当于交换R[i]和R[j]，交换后j指针减1
*/
}
/*
endwhile
*/
R[i]=pivot;
/*
基准记录已被最后定位*/
return
i;
}
/*
end
of
partition
*/
void
Quick_Sort(int
low,int
high)
{
/*
对R[low..high]快速排序
*/
int
pivotpos;
/*
划分后的基准记录的位置
*/
if(low<high){/*
仅当区间长度大于1时才须排序
*/
pivotpos=Partition(low,high);
/*
对R[low..high]做划分
*/
Quick_Sort(low,pivotpos-1);
/*
对左区间递归排序
*/
Quick_Sort(pivotpos+1,high);
/*
对右区间递归排序
*/
}
}
/*
end
of
Quick_Sort
*/
void
main()
{
int
i,n;
puts("Please
input
total
element
number
of
the
sequence:");
scanf("%d",&n);
if(n<=0||n>MAX)
{
printf("n
must
more
than
0
and
less
than
%d.\n",MAX);
exit(0);
}
puts("Please
input
the
elements
one
by
one:");
for(i=1;i<=n;i++)
scanf("%d",&R[i]);
puts("The
sequence
you
input
is:");
for(i=1;i<=n;i++)
printf("%4d",R[i]);
Quick_Sort(1,n);
puts("\nThe
sequence
after
quick_sort
is:");
for(i=1;i<=n;i++)
printf("%4d",R[i]);
puts("\n
Press
any
key
to
quit...");
}
//LZ仔细研究研究

Ⅷ C语言算法设计，选择排序

排序如下：

voidSelectSort(RecordTyper[],intlength)/*对记录数组r做简单选择排序，length为待排序记录的个数*/

{inttemp;for(i=0;i<length-1;i++)//n-1趟排序{intindex=i；//假设index处对应的数组元素是最小的for(intj=i+1;j<length;j++)//查找最小记录的位置if(r[j].key<r[index].key)index=j;if(index!=i)//若无序区第一个元素不是无序区中最小元素，则进行交换{temp=r[i];r[i]=r[index];r[index]=temp;}}}

初始序列：{49 27 65 97 76 12 38}第1趟：12与49交换：12{27 65 97 76 49 38}第2趟：27不动：12 27{65 97 76 49 38}第3趟：65与38交换：12 27 38{97 76 49 65}第4趟：97与49交换：12 27 38 49{76 97 65}第5趟：76与65交换：12 27 38 49 65{97 76}第6趟：97与76交换：12 27 38 49 65 76 97 完成

选择排序法 是对 定位比较交换法（也就是冒泡排序法） 的一种改进。选择排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。

简单选择排序的基本思想：第1趟，在待排序记录r[1]~r[n]中选出最小的记录，将它与r[1]交换；第2趟，在待排序记录r[2]~r[n]中选出最小的记录，将它与r[2]交换；以此类推，第i趟在待排序记录r[i]~r[n]中选出最小的记录，将它与r[i]交换，使有序序列不断增长直到全部排序完毕。

拓展资料

下面也写个例子：

由大到小时：

intmain(void){inta[10];inti,j,t,k;for(i=0;i<10;i++)scanf("%d",&a[i]);/*输入10个数，比武报名，报名费用10000￥^_^*/for(i=0;i<9;i++)/*10个数，所以只需比9次*/{k=i;/*裁判AND记者实时追踪报道比赛情况*/for(j=i+1;j<10;j++)if(a[k]<a[j])k=j;/*使a[k]始终表示已比较的数中的最大数*/if（k！=i）{t=a[i];a[i]=a[k];a[k]=t;}/*t发放奖品*/}for(i=0;i<10;i++)printf("%4d",a[i]);/*显示排序后的结果*/return0;}

由小到大时：

intmain(void){inta[10];inti,j,t,k;for(i=0;i<10;i++)scanf("%d",&a[i]);/*输入10个数，比武报名，报名费用10000￥^_^*/for(i=0;i<9;i++){k=i;/*裁判AND记者实时追踪报道比赛情况*/for(j=i+1;j<10;j++)if(a[k]>a[j])k=j;if（k！=i）{t=a[i];a[i]=a[k];a[k]=t;}/*t发放奖品*/}for(i=0;i<=9;i++)printf("%4d",a[i]);/*显示排序后的结果*/return0;}

Ⅸ 算法设计, 用代码完成三种简单的排序方法(冒泡,简单插入,简单选择)中的任何一个即可

排序算法是最基础的算法，冒泡算法如下：
void buble_sort(int arr[], int length)
{
int i, j, max;
for(i=0, i<length-1, i++)
{
for(j=0, j<length-i-1, j++)

{
if(a[j]>a[j+1])

{

max = a[j];

a[j] = a[j+1];

a[j+1] = max;

}

}

}
}

Ⅹ 请高手帮忙设计一个排序算法

凡是排序算法都要有一个确定顺序先后的方法，在排序过程都要借助这个方法来确定先后。
你可以先做个函数compare(a, b)，如果按照规则a排在b前则返回True否则False，然后再用快速排序来做排序，冒泡法的效率很低。

貌似还要有字符间比较的方法compare2(a, b)

根据你给的样例，compare(a, b)应按照如下规则运行:
1. 如果a包含的字符数量少于b，返回True.
2. 如果b包含的字符数量少于a，返回False.
3. 逐字符比较a和b，根据compare2(a, b)的返回值：如果为Same继续比较，否则返回compare2的返回值.
4. 如果a、b相同，返回True.