精华内容
下载资源
问答
  • 2.任务:设计一个内部排序算法模拟系统,利用该系统实现常用的7种排序算法,并测试各种排序算法的性能。 二、内容、要求与安排方式 1.实验内容:通过一个简单的菜单,分别实现下列排序要求,采用组不同数据测试...

    实验四 常用的内部排序算法
    实验学时:2 实验类型:综合型
    一、目的与任务
    1.目的:掌握常见的内部排序算法的思想及其适用条件;掌握常见的内部排序算法的程序实现。
    2.任务:设计一个内部排序算法模拟系统,利用该系统实现常用的7种排序算法,并测试各种排序算法的性能。
    二、内容、要求与安排方式
    1.实验内容:通过一个简单的菜单,分别实现下列排序要求,采用几组不同数据测试各排序算法的性能(比较次数和移动次数)及稳定性。
     实现简单选择排序、直接插入排序和冒泡排序;
     实现折半插入排序;
     实现希尔排序算法;
     实现快速排序算法(递归和非递归);
     实现堆排序算法。
    2.输入和输出:
    (1)输入形式:根据菜单提示选择排序算法,输入一组带排序数据。
    (2)输出形式:输出排序结果(体现排序过程),及排序过程中数据的比较次数和移动次数,判断排序算法的稳定性。
    3.实验要求:
     实现一个简单的交互式界面,包括系统菜单、清晰的输入提示等。
     要输出每一趟排序的结果。
     能够上机编辑、调试出完整的程序。
    4.实验安排方式:
     在实验课前编写出完整程序,在实验课时进行调试;
     每组1人,独立完成上机实验。
    三、注意事项:
    1.数据类型定义
    #define MAXSIZE 100 /参加排序元素的最大个数/
    typedef int KeyType;
    typedef struct {
    KeyType key;
    InfoType otherinfo; // 其他字段(自己设计)
    }RedType;
    typedef struct
    {
    RedType r[MAXSIZE+1];
    int length; /参加排序元素的实际个数/
    }SqList;
    2.注意理解各种算法的思想、了解算法的适用情况及时间复杂度,能够根据实际情况选择合适的排序方法。

    【实现思路】
    各种排序的实现
    重点:通过采用ispt参数标记是否输出过程
    性能测试在数据规模到达600就会爆掉,因为插排本身的问题
    递归快排的过程输出不是很合理,有重复

    solve.h
    #include <bits/stdc++.h>
    using namespace std;
    #ifndef SOLVE_H_INCLUDED
    #define SOLVE_H_INCLUDED
    
    #define MAXSIZE 100000 /*参加排序元素的最大个数*/
    typedef  int  KeyType;
    typedef struct {
        KeyType  key;
        KeyType  value;  // 其他字段(自己设计)
    }RedType;
    typedef struct{
        RedType  r[MAXSIZE+1];
        int        length; /*参加排序元素的实际个数*/
    }SqList;
    typedef struct{//每种排序的交换次数与排序次数
        int CompareCount;
        int SwapCount;
    }Status;
    //选择排序
    Status ChoiceSort(SqList data,bool ispt);
    //插入排序
    Status InsertSort(SqList data,bool ispt);
    //冒泡排序
    Status BubbleSort(SqList data,bool ispt);
    //折半排序
    Status ErSort(SqList data,bool ispt);
    //希尔排序
    Status ShellSort(SqList data,bool ispt);
    //堆排序
    void MaxSort(SqList & data, int i, int n,int & com,int & swp);
    Status HeapSort(SqList data,bool ispt);
    //快速排序
    int Partition(SqList & data, int left, int right,int & com,int & swp);
    void Quickly(SqList & data,int left,int right,int & com,int & swp,bool ispt);
    Status QSort(SqList data,bool ispt);
    Status RQSort(SqList data,bool ispt);
    //打印过程
    void PrintKey(SqList data);
    //打印数据
    void PrintData(SqList data);
    //比较数据 (>:1 <:-1 == 0)
    int CompareData(RedType a,RedType b);
    //交换数据
    void SwapData(RedType & a,RedType & b);
    //随机生成数据
    void RandData(SqList & data);
    //输入数据
    void InputData(SqList & data);
    //界面
    void welcome();
    #endif // SOLVE_H_INCLUDED
    
    
    main.cpp
    #include <bits/stdc++.h>
    #include "solve.h"
    using namespace std;
    //原始数据
    SqList oldData;
    //临时数据
    SqList tempData;
    //排序属性
    Status status;
    //排序性能测试
    void Test();
    int main()
    {
        int order = -1;
        bool flag = true;
    
    //cout<<"\t1.生成测试数据\t2.录入测试数据"<<endl;
    //cout<<"\t3.选择排序\t4.插入排序"<<endl;
    //cout<<"\t5.冒泡排序\t6.折半排序"<<endl;
    //cout<<"\t7.希尔排序\t8.堆排序"<<endl;
    //cout<<"\t9.递归快排\t10.非递快排"<<endl;
    //cout<<"\t11.各种排序的性能测试"<<endl;
        while(1){
            welcome();
            cout<<"请输入命令:";
            cin>>order;
            switch(order){
            case 1:
                RandData(oldData);
                PrintData(oldData);
                break;
            case 2:
                InputData(oldData);
                PrintData(oldData);
                break;
            case 3:
                tempData = oldData;
                status = ChoiceSort(tempData,true);
                cout<<"比较次数:"<<status.CompareCount<<endl;
                cout<<"交换次数:"<<status.SwapCount<<endl;
                break;
            case 4:
                tempData = oldData;
                status = InsertSort(tempData,true);
                cout<<"比较次数:"<<status.CompareCount<<endl;
                cout<<"交换次数:"<<status.SwapCount<<endl;
                break;
            case 5:
                tempData = oldData;
                status = BubbleSort(tempData,true);
                cout<<"比较次数:"<<status.CompareCount<<endl;
                cout<<"交换次数:"<<status.SwapCount<<endl;
                break;
            case 6:
                tempData = oldData;
                status = ErSort(tempData,true);
                cout<<"比较次数:"<<status.CompareCount<<endl;
                cout<<"交换次数:"<<status.SwapCount<<endl;
                break;
            case 7:
                tempData = oldData;
                status = ShellSort(tempData,true);
                cout<<"比较次数:"<<status.CompareCount<<endl;
                cout<<"交换次数:"<<status.SwapCount<<endl;
                break;
            case 8:
                tempData = oldData;
                status = HeapSort(tempData,true);
                cout<<"比较次数:"<<status.CompareCount<<endl;
                cout<<"交换次数:"<<status.SwapCount<<endl;
                break;
            case 9:
                tempData = oldData;
                status = QSort(tempData,true);
                cout<<"比较次数:"<<status.CompareCount<<endl;
                cout<<"交换次数:"<<status.SwapCount<<endl;
                break;
            case 10:
                tempData = oldData;
                status = RQSort(tempData,true);
                cout<<"比较次数:"<<status.CompareCount<<endl;
                cout<<"交换次数:"<<status.SwapCount<<endl;
                break;
            case 11:
                Test();
                break;
            default:
                break;
            }
        }
        return 0;
    }
    void Test(){
        cout<<"============================================================="<<endl;
    	tempData = oldData;
    	status = ChoiceSort(tempData,false);
    	cout<<"============选择排序==========="<<endl;
    	cout<<"比较次数:"<<status.CompareCount<<endl;
    	cout<<"交换次数:"<<status.SwapCount<<endl;
    
    	tempData = oldData;
    	status = InsertSort(tempData,false);
        cout<<"============插入排序==========="<<endl;
    	cout<<"比较次数:"<<status.CompareCount<<endl;
    	cout<<"交换次数:"<<status.SwapCount<<endl;
    
    	tempData = oldData;
    	status = BubbleSort(tempData,false);
        cout<<"============冒泡排序==========="<<endl;
    	cout<<"比较次数:"<<status.CompareCount<<endl;
    	cout<<"交换次数:"<<status.SwapCount<<endl;
    
    	tempData = oldData;
    	status = ErSort(tempData,false);
    	cout<<"============折半排序==========="<<endl;
    	cout<<"比较次数:"<<status.CompareCount<<endl;
    	cout<<"交换次数:"<<status.SwapCount<<endl;
    
    	tempData = oldData;
    	status = ShellSort(tempData,false);
    	cout<<"============希尔排序==========="<<endl;
    	cout<<"比较次数:"<<status.CompareCount<<endl;
    	cout<<"交换次数:"<<status.SwapCount<<endl;
    
    	tempData = oldData;
    	status = HeapSort(tempData,false);
    	cout<<"============堆排序==========="<<endl;
    	cout<<"比较次数:"<<status.CompareCount<<endl;
    	cout<<"交换次数:"<<status.SwapCount<<endl;
    
    	tempData = oldData;
    	status = QSort(tempData,false);
        cout<<"============递归快排==========="<<endl;
    	cout<<"比较次数:"<<status.CompareCount<<endl;
    	cout<<"交换次数:"<<status.SwapCount<<endl;
    
    	tempData = oldData;
    	status = RQSort(tempData,false);
    	cout<<"============非递快排==========="<<endl;
    	cout<<"比较次数:"<<status.CompareCount<<endl;
    	cout<<"交换次数:"<<status.SwapCount<<endl;
        cout<<"============================================================="<<endl;
    
    }
    
    
    展开全文
  • 数 据 结 构 实 验 报 告 实验题目几种基本排序算法的实现 耀 班级 计嵌 151 学号 1513052017 Word 资料 一 实验目的 实现直接插入排序冒泡排序简单选择排序快速排序希尔 排序堆排序等 6 种常用排序算法比较各算法...
  • 结 构 实 据 数验 告报 实验题目几种基本排序算法的实现 耀 151 班级 计嵌 1513052017 学号 资料Word 一 实验目的 实现直接插入排序冒泡排序简单选择排序快速排序希尔排序堆排序等6种常用排序算法比较各算法比较...
  • 排序算法的归类:总的排序算法分为以下类:1.插入类排序:如:直接插入排序,折半插入排序,希尔排序2.交换类排序:如:冒泡排序,快速排序,其中冒泡排序应该是计算机专业的学生最为熟悉的一排序算法了,而快速...

    一、 实验目的

    1. 掌握各种常用排序的算法思想;

    2. 掌握各种常用排序的算法实现;

    3. 掌握各种常用排序时间复杂度,比较各种排序的优缺点。

    二.排序算法的归类:

    总的排序算法分为以下几类:

    1.插入类排序:如:直接插入排序,折半插入排序,希尔排序

    2.交换类排序:如:冒泡排序,快速排序,其中冒泡排序应该是计算机专业的学生最为熟悉的一种排序算法了,而快速排序则是在冒泡排序的基础上一次消除多个逆序对改进而来

    3.选择类排序:如:简单选择排序,堆排序。

    4.其它类排序:如:归并排序,基数排序等。


    三、 实验内容与要求

    1. 编程实现各种排序算法,并对比各种算法的效率。

    【设计要求】在给出的代码素材sort.cpp文件中补充main函数中的swtich语句,以及以下排序函数,并比较各种排序方法在对素材文件中的1.data~5.data待排序序列进行排序时所需要的时间。

    void shellsort(int data[],int n);//希尔排序

    void bubllesort(int data[],int n);//冒泡排序

    void quicksort(int data[],int n);//快速排序

    void selectsort(int data[],int n);//简单选择排序

    void heapsort(int data[],int n);//堆排序

    void mergesort(int data[],int n);//合并排序

    void radixsort(int data[],int n) ;//基数排序

    2.【程序代码】完成createdata函数及排序函数,其中createdata可参考下图,其中往目标文件中写入两部分内容,随机数的总个数及产生各个随机数。


    方法一:C++

    1. sort.h

    #include<iostream>
    #include<fstream>
    #include<stdlib.h>
    using namespace std;
    const int LineLenght=20;//控制屏幕打印时,每行元素个数 
    class sort
    {
    	private:
    		int *data,n;
    	public:
    		void Printdata();
    		void Getdata(string file);
    		void creatdata(int num);
    		void Outputdata(); 
    		void insertsort();//直接插入排序 
    		void shellsort();//希尔排序 
    		void bubllesort();//冒泡排序 
    		void quicksort(int low, int high);//快速排序
    		void selectsort();//简单选择排序
    		void heapsort();//堆排序
    		void sift(int start,int endnode);
    		void mergesort();//合并排序
    		void merge(int low, int high,int temp[]);
    		void radixsort();//基数排序
    };

    2. sort.cpp



    #include<iostream>
    #include<fstream>
    #include<stdlib.h>
    #include"sort.h"
    using namespace std;
    //======打印=============================================================
    void sort::Printdata( )
    {
    	 for(int i=1;i<=n;i++)
    	{
         cout<<data[i]<<" ";
    	   if(i%LineLenght==LineLenght-1)
    	     cout<<endl;
        } 
       cout<<endl;	 
    }
    //========读取数据=========================================================
    void sort::Getdata(string file)
    {
    	
    	ifstream read(file);
    	if (!read) 
    		{
    		cout << "\n\t文件读取错误!!!\n\n"; system("pause");
    		}
    	else 
    	{
    		read>>n;
    		data = new int[n + 1];
    		for(int i=1;i<=n;i++)
    			read>>data[i];
    	}
    	read.close();
    }
    //========生成随机数据=====================================================
    void sort::creatdata(int num)
    {
    	ofstream write("in.txt");
    	write<<num<<endl;
    	for(int i=0;i<num;i++)
    	{
    		write<<rand()%1000+1<<" ";
    	}
    	write.close();
    
    }
    //========写出排序后的数据=================================================
    void sort::Outputdata( )
    {
    	ofstream write("out.txt");
    	write<<n<<endl;
    	for(int i=1;i<=n;i++)
    	{
    		write<<data[i]<<" ";
    	}
    }
    //=========================排序方法======================================
    
    //========直接插入排序=====================================================
    void sort::insertsort()
    {
    	for (int i = 2; i <= n; i++)
    	{
    		data[0] = data[i];
    			int j;
    			for (j = i - 1; j>0 && data[0] < data[j]; j--)
    				data[j + 1] = data[j];
    			data[j+1] = data[0];
    		
    	}
    }
    
    //=======希尔排序==========================================================
    void sort::shellsort()
    {
    	for (int d=n/2; d>0; d/=2)
    	{
    		for (int i = 1 + d; i <= n; i++)
    		{
    			data[0] = data[i]; 
    			int j;
    			for (j = i - d; j>0 && data[0] < data[j]; j -= d)
    				data[j + d] = data[j];
    			data[j + d] = data[0];
    		}
    	} 
    }
    
    //======冒泡排序===========================================================
    void sort::bubllesort()
    {
    	int flag=1;
    	for (int i = 1; i <= n&&flag; i++)
    	{
    		flag = 0;
    		for (int j = 1; j <= n-i; j++)
    		{
    			if (data[j] > data[j + 1])
    			{
    				int temp = data[j+1];
    				data[j + 1] = data[j];
    				data[j] = temp;
    				flag = 1;
    			}
    		}
    	}
    }
    
    //====快速排序=============================================================
    void sort::quicksort(int low,int high)
    {
    		int i = low, j = high;
    		if (low>high)
    			return;
    		data[0] = data[low];
    		while (i != j)
    		{
    			while (data[j] >= data[0] && i < j)
    				j--;
    			while (data[i] <= data[0] && i < j)
    				i++;
    			if (i < j)
    			{
    				int temp = data[i];
    				data[i] = data[j];
    				data[j] = temp;
    			}
    		}
    		data[low] = data[i];
    		data[i] = data[0];
    		quicksort(low, i - 1);//左
    		quicksort(i + 1, high);//右
    }
    
    //==========简单选择排序===================================================
    void sort::selectsort()
    {
    	for (int i = 1; i <= n; i++)
    	{
    		int min = i;
    		data[0] = data[i];
    		for (int j = i + 1; j <= n; j++)
    		{
    			if (data[j] < data[min]) 
    				min = j;
    		}
    		if (min != i)
    		{
    			data[i] = data[min];
    			data[min] = data[0];
    		}
    	}
    }
    //================堆排序===================================================
    void sort::heapsort()
    {
    	for (int i = n / 2-1; i >= 1; i--)
    		sift(i,n);
    	for (int i = n; i > 1; i--)
    	{
    		data[0] = data[1];
    		data[1] = data[i];
    		data[i] = data[0];
    		sift(1,i-1);
    	}
    }
    void sort::sift(int start,int end)
    {
    	data[0] = data[start];
    	int sonode = 2 * start;
    	while (sonode <= end)
    	{
    		if (sonode + 1 <= end&&data[sonode + 1] > data[sonode])
    			sonode++;
    		if (data[sonode] <= data[0]) break;
    		data[start] = data[sonode];
    		start = sonode;
    		sonode = 2 * start;
    	}
    	data[start] = data[0];
    }
    //============归并排序=====================================================
    void sort::merge(int low, int high,int temp[])
    {
    	
    	if (high <= low)
    		return;
    	int mid = (high +low) / 2;
    	merge(low, mid,temp);
    	merge(mid+1, high,temp);	
    	
    	int i = low, j = mid + 1;
    	for (int k = low; k <= high; k++)
    		temp[k] = data[k];
    	for (int k = low; k <= high; k++)
    	{
    		if (i > mid)
    			data[k] = temp[j++];
    		else if (j > high)
    			data[k] = temp[i++];
    		else if (temp[i] <= temp[j])
    			data[k] = temp[i++];
    		else
    			data[k] = temp[j++];
    	}
    }
    void sort::mergesort()
    {
    	int *temp = new int[n + 1];//辅助数组
    	merge( 1 , n, temp);
    }
    
    //===========基数排序======================================================
    void sort::radixsort()
    {
    	int maxbit=4;//最大位数为4
    	int *temp = new int[n + 1];
    	int count[10];
    	int radix = 1;
    	for (int i = 0; i < maxbit; i++)
    	{
    		for (int j = 0; j < 10; j++)
    			count[j] = 0;
    		for (int j = 1; j <= n; j++)
    		{
    			int bit = (data[j] / radix) % 10;
    			count[bit]++;
    		}
    		for (int j = 1; j < 10; j++)
    			count[j] = count[j - 1] + count[j];
    		for (int j = n; j > 0; j--) //将所有桶中记录依次收集到temp中  
    		{
    			int bit = (data[j] / radix) % 10;
    			temp[count[bit]] = data[j];
    			count[bit]--;
    		}
    		for (int j = 1; j <= n; j++) //将temp数组的内容复制到data中  
    			data[j] = temp[j];
    		radix = radix * 10;
    	}
    }

    3. main.cpp

    #include<iostream>
    #include<fstream>
    #include<stdlib.h>
    #include<time.h>
    #include"sort.h"
    using namespace std;
    int menu();
    void carte( sort Sort,int choice,string file,int n);
    void print( sort Sort,int time);
    void choicefile(string &file,int &n);
    void main()
    {
    	srand((unsigned int)(time(NULL)));
    	int choice,n = 10000;
    	string file;
    	sort Sort;	
    	Sort.creatdata(n);
    	choicefile(file, n);
    	do{
    		choice=menu();
    		carte(Sort, choice,file,n);
    	} while (choice != 0);
    }
    
    int menu()
    {
    	int choice;
    	cout << "0.  退出\n1.  直接插入排序\n2.  希尔插排序\n3.  冒泡排序\n4.  快速排序\n5.  简单选择插入排序\n6.  堆排序\n7.  归并排序\n8.  基数排序\n";
    	cout << endl << "请选择排序方式:"; cin >> choice;
    	return choice;
    }
    void print(sort Sort,int time)
    {
    	Sort.Printdata();//打印
    	Sort.Outputdata();//写出
    	cout << "排序时间为" <<time << "毫秒" << endl;
    	cout << "您可以尝试一下其它的排序方法:\n";
    }
    void carte(sort Sort,int choice,string file,int n)
    {
    	clock_t start, end;
    	switch (choice)
    	{
    	case 0:break;
    	case 1:{
    			   system("cls");
    			   Sort.Getdata(file);//读取
    			   start = clock();
    			   Sort.insertsort();//排序
    			   end = clock();
    			   print(Sort, end - start); }
    		break;
    	case 2:{
    			   system("cls");
    			   Sort.Getdata(file);
    			   start = clock();
    			   Sort.shellsort();
    			   end = clock();
    			   print(Sort, end - start); }
    		break;
    	case 3:{
    			   system("cls");
    			   Sort.Getdata(file);
    			   start = clock();
    			   Sort.bubllesort();
    			   end = clock();
    			   print(Sort, end - start); }
    		break;
    	case 4:{
    			   system("cls");
    			   Sort.Getdata(file);
    			   start = clock();
    			   Sort.quicksort(1, n);
    			   end = clock();
    			   print(Sort, end - start); }
    		break;
    	case 5:{
    			   system("cls");
    			   Sort.Getdata(file);
    			   start = clock();
    			   Sort.selectsort();
    			   end = clock();
    			   print(Sort, end - start); }
    		break;
    	case 6:{
    			   system("cls");
    			   Sort.Getdata(file);
    			   start = clock();
    			   Sort.heapsort();
    			   end = clock();
    			   print(Sort, end - start); }
    		break;
    	case 7:{
    			   system("cls");
    			   Sort.Getdata(file);
    			   start = clock();
    			   Sort.mergesort();
    			   end = clock();
    			   print(Sort, end - start); }
    		break;
    	case 8:{
    			   system("cls");
    			   Sort.Getdata(file);
    			   start = clock();
    			   Sort.radixsort();
    			   end = clock();
    			   print(Sort, end - start); }
    		break;
    	default:
    		cout << "没有这种排序方式,请选择正确的排序方法:\n\n";
    	}
    }
    void choicefile(string &file,int &n)
    {
    	int choice;
    	ifstream in;
    	cout << "选择排序文件:\n";
    	cout << "\t1.	in.txt\n\t2.	1.txt\n\t3.	2.txt\n";
    	cin >> choice;
    	switch (choice)
    	{
    	case 1:file = "in.txt"; break;
    	case 2:file = "1.txt";
    		in.open(file,ios::beg);
    		in >> n;
    		in.close();break;
    	case 3:file = "2.txt"; 
    		in.open(file,ios::beg);
    		in >> n;
    		in.close(); break;
    	default:cout << "\n\t找不到文件!!!\n\n"; system("pause");
    	}
    	system("cls");
    }

    #include "sort.h"方法二:C

    1. sort.h

    素材包含,此处略

    2. sort.cpp

    #include <algorithm>
    #include <string.h>
    void Printdata(int data[],int n)
    {
        for(int i=0;i<n;i++)
    	{
           printf("%4d",data[i]);
    	   if(i%LineLenght==LineLenght-1)
    	      printf("\n");	
        } 
        printf("\n");	
    	return;                           
    }
    
    int Getdata(int data[], int &n)
    {   
        
    	FILE *fp;
        if ((fp = fopen(SOURCEFILE,"r")) == NULL) /* 以读方式打开文本文件 */
    	{
    		printf("Failure to open score.txt!\n");
    		return 0;//读数据失败 
    	}
    	int i=0;
    	fscanf(fp,"%6d",&n);//获取文件中的元素个数 
    	 
    	while(!feof(fp)&&i<n)
    	{
    	   fscanf(fp,"%10d",&data[i]);
    	   i++; 
    	} 
    	fclose(fp); 
        return 1;  //成功读数据                          
    }
    
    void insertsort(int data[], int n)//直接插入排序 
    {   
    	for(int i = 1, j; i < n; i++) {
            int x = data[i];
    		for(j = i-1; j >= 0; j--) {
    		   if(data[j] > x)
    		     data[j+1] = data[j];
    		   else break;
    		}
    		if(j != i) data[j+1] = x;
    	}
    } 
    
    void creatdata(int &n)
    {
    	FILE *p;
    	p = fopen(SOURCEFILE, "w");
    	srand((unsigned)time(NULL));
    	if (p == NULL) {
    		printf("创建文件失败!");
    	} else {
    		fprintf(p, "%6d", n);
    		for (int i = 0; i < n; i++) {
    			int num = rand() % 1000 + 1;
    			fprintf(p, "%10d", num);
    		}
    		fclose(p);
    	}
    }
    
    int Outputdata(int data[],int n)
    {
    	FILE *fp;
    	if ((fp = fopen("out.txt","w")) == NULL) /* 以写方式打开文本文件 */
    	{
    		printf("Failure to open score.txt!\n");
    		return 0;//写数据失败 
    	}
    	for(int i=0;i<n;i++)  
            fprintf(fp,"%10d",data[i]);
    	fclose(fp);
    	return 1;
    	
    }
    
    void shellsort(int data[],int n)//希尔排序 
    {  
    	for (int gap = n / 2; gap > 0; gap /= 2) {
    		for (int i = 0; i < gap; i++) {
    			for (int j = i + gap; j < n; j += gap) {
    				if (data[j] < data[j-gap]) {
    					int temp = data[j], k = j - gap;
    					while (k >= 0 && data[k] > temp) {
    						data[k + gap] = data[k];
     						k -= gap;
    					}
    					data[k + gap] = temp;
    				}
    			}
    
    		}
    	}
    }
    
    void bubllesort(int data[],int n)//冒泡排序 
    { 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (data[j] > data[j+1]) {
                    std::swap(data[j+1], data[j]);
                }
            }
        }
    }
    
    void quicksort(int data[], int n, int low, int high) //快速排序 
    {  
    	if (low < high) {
    		int temp = data[low], l = low, r = high-1;
    		while (l < r) {
    			while (l < r && data[r] > temp) r--;
    			if (l < r)
    				data[l++] = data[r];
    			while (l < r && data[l] < temp) l++;
    			if (l < r)
    				data[r--] = data[l];
    		}
    		data[l] = temp;
    		quicksort(data, n, low, l-1);
    		quicksort(data, n, l+1, high);
    	}
    }
    
    void selectsort(int data[],int n)//简单选择排序 
    {  
        for (int i = 0; i < n; i++) {
            int index = i;
            for (int j = i + 1; j < n; j++) {
                if (data[j] > data[index]) {
                    index = j;
                }
            }
            if (index != i) std::swap(data[index], data[i]);
        }
    }
    
    void heapAdjustDown(int *arr, int start, int end) {
        int temp = arr[start];
        int i = 2 * start + 1;
        while (i <= end) {
            if (i + 1 <= end && arr[i + 1] > arr[i]) i++;
            if (arr[i] <= temp) break;
            arr[start] = arr[i];
            start = i;
            i = 2 * start + 1;
        }
        arr[start] = temp;
    }
    
    void heapsort(int data[],int n)//堆排序 
    {  
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapAdjustDown(data, i, n - 1);
        }
        for (int i = n - 1; i > 0; i--) {
            std::swap(data[i], data[0]);
            heapAdjustDown(data, 0, i - 1);
        }
    }
    
    void merge(int *data, int start, int end, int *result) {
        int left_length = (end - start + 1) / 2 + 1;
        int left_index = start;
        int right_index = start + left_length;
    
        int result_index = start;
        while (left_index < start + left_length && right_index < end + 1) {
            if (data[left_index] <= data[right_index])
                result[result_index++] = data[left_index++];
            else
                result[result_index++] = data[right_index++];
        }
        while (left_index < start + left_length)
            result[result_index++] = data[left_index++];
        while (right_index < end + 1)
            result[result_index++] = data[right_index++];
    }
    
    void mergesort(int data[], int start, int end, int *result) //合并排序
    {   
        /*for (int i = 0; i < 10; i++)
            printf("%d ", data[i]);
        puts("");*/
        if (end - start == 1) {
            if (data[start] > data[end]) std::swap(data[start], data[end]);
            return;
        }
        else if (end == start) return;
        else {
            mergesort(data, start, (end-start+1)/2+start, result);
            mergesort(data, (end - start + 1) / 2 + start+1, end, result);
            merge(data, start, end, result);
            for (int i = start; i <= end; i++) {
                data[i] = result[i];
            }
        }
    }
    
    int maxbit(int data[], int n)  //确定基数排序的关键字个数
     {
        int d = 1, p = 10;
        for (int i = 0; i < n; i++) {
            while (data[i] >= p) {
                p *= 10;
                ++d;
            }
        }
        return d;
    }
    
    void radixsort(int data[], int n)//基数排序
    {  
        int d = maxbit(data, n);
        int temp[MaxSize], count[10], radix = 1;
        for (int i = 1; i <= d; i++) {
            memset(count, 0, sizeof(count));
    
            for (int j = 0; j < n; j++) {
                int k = (data[j] / radix) % 10;
                count[k]++;
            }
    
            for (int j = 1; j < 10; j++) {
                count[j] += count[j - 1];
            }
            for (int j = n - 1; j >= 0; j--) {
                int k = (data[j] / radix) % 10;
                temp[count[k] - 1] = data[j];
                count[k]--;
            }
            for (int j = 0; j < n; j++) {
                data[j] = temp[j];
            }
            radix *= 10;
        }
    }

    3. main.cpp

    #include "sort.h"
    int main()
    {
    	int n=10;	
    	int data[MaxSize];
        clock_t start,end; 
    	creatdata(n);
        Getdata( data, n); //读取文件的数据存放在data数组中  
    	int menu;
        printf("请选择排序方式:\n");
    	while(1) {
    	    printf("1.  直接插入排序\n");
    	    printf("2.  希尔插排序\n");
    	    printf("3.  冒泡排序\n");
    	    printf("4.  快速排序\n");
    	    printf("5.  简单选择插入排序\n");
    	    printf("6.  堆排序\n");
    	    printf("7.  归并排序\n");
    	    printf("8.  基数排序\n");
    	    scanf("%d",&menu);
    	    switch(menu)
    	    {
    	    	case 1:{
    	    		start = clock();
    	    		insertsort(data, n);
    	    		end = clock();
    	    		Printdata(data ,n);//在屏幕上输出数据 
    	    		Outputdata(data ,n);//输出至文件
    	    		printf("排序时间为%d毫秒",end-start);
    	    		printf("您可以尝试一下其它的排序方法:\n");
    	    		break;
    	    	}	    		
    			case 2 : {
    				start = clock();
    	    		shellsort(data, n);
    	    		end = clock();
    	    		Printdata(data ,n);//在屏幕上输出数据 
    	    		Outputdata(data ,n);//输出至文件
    	    		printf("排序时间为%d毫秒",end-start);
    	    		printf("您可以尝试一下其它的排序方法:\n");
    	    		break;
    			}
    			case 3 : {
    				start = clock();
    	    		bubllesort(data, n);
    	    		end = clock();
    	    		Printdata(data ,n); 
    	    		Outputdata(data ,n);
    	    		printf("排序时间为%d毫秒",end-start);
    	    		printf("您可以尝试一下其它的排序方法:\n");
    	    		break;
    			}
    			case 4 : {
    				start = clock();
    				quicksort(data, n, 0, n);
    	    		end = clock();
    	    		Printdata(data ,n); 
    	    		Outputdata(data ,n);
    	    		printf("排序时间为%d毫秒",end-start);
    	    		printf("您可以尝试一下其它的排序方法:\n");
    	    		break;
    			}
                case 5: {
                    start = clock();
                    selectsort(data, n);
                    end = clock();
                    Printdata(data, n);
                    Outputdata(data, n);
                    printf("排序时间为%d毫秒", end - start);
                    printf("您可以尝试一下其它的排序方法:\n");
                    break;
                }
    
                case 6: {
                    start = clock();
                    heapsort(data, n);
                    end = clock();
                    Printdata(data, n);
                    Outputdata(data, n);
                    printf("排序时间为%d毫秒", end - start);
                    printf("您可以尝试一下其它的排序方法:\n");
                    break;
                }
                case 7: {
                    start = clock();
                    int result[MaxSize];
                    mergesort(data, 0, n-1, result);
                    end = clock();
                    Printdata(result, n);
                    Outputdata(result, n);
                    printf("排序时间为%d毫秒", end - start);
                    printf("您可以尝试一下其它的排序方法:\n");
                    break;
                }
                case 8: {
                    start = clock();
                    radixsort(data, n);
                    end = clock();
                    Printdata(data, n);
                    Outputdata(data, n);
                    printf("排序时间为%d毫秒", end - start);
                    printf("您可以尝试一下其它的排序方法:\n");
                    break;
                }
    			default: {
    				printf("没有这种排序方式,请选择正确的排序方法:\n");
    			   
    			}
    	    
    	    }
        }
        return 0;
    }



    展开全文
  • (1)掌握线性表的存储方式,并在此基础上实现典型的排序算法 (2)理解并掌握内部排序中几种常用算法的性能和适用场合 (3)理解并比较各种排序算法的时间复杂度和空间复杂度

    一、实验要求

    (1)对N个数进行排序并测试
    (2)用直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序这7种算法进行排序
    (3)比较各种排序算法的时间复杂度和空间复杂度
    (4)尝试算法的改进

    二、实验过程

    对N个数(N大于2000),从直接插入排序、折半插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序这7种算法中选取4种排序算法进行排序。
    1.设计合适的数据结构存储这N个数。
    2.对这N个数分别用下列三种情况进行测试:
    (1)N个从小到大的有序整数
    (2)N个从大到小的有序整数
    (3)N个随机产生的无序数
    3.比较各类排序算法的时间复杂度和空间复杂度。
    4.对上述算法提出改进之处(创新思维)。

    三、实验代码
    选用的结构体是顺序表,其中的last其实在后面没有作用,只是用作与初始化用。

    typedef int DataType;
    typedef struct{
    	DataType data[MAXSIZE];
    	int last;
    }node;
    

    完整代码

    #include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #include <string.h>
    #define MAXSIZE 2001
    typedef int DataType;
    //结构体函数 
    typedef struct{
    	DataType data[MAXSIZE];
    	int last;
    }node;
    //初始化顺序表 
    void initlist(node *r){
    	r->last=0;
    }
    //无序版本的顺序表 
    void putNum(node *r){
    	initlist(r);
    	srand(time(0));
    	int i;
    	for(i=1;i<MAXSIZE;i++){
    		r->data[i]=rand();
    	}
    }
    //升序版本的顺序表 
    void putNumshen(node *r){
    	initlist(r);
    	int i;
    	for(i=1;i<MAXSIZE;i++){
    		r->data[i]=i;
    	}
    }
    //降序版本的顺序表 
    void putNumjiang(node *r){
    	initlist(r);
    	int i;
    	int n=MAXSIZE;
    	for(i=1;i<MAXSIZE;i++){
    		r->data[i]=n;
    		n--;
    	}
    }
    //测试使用,用于输出较少的测试 
    void shuchu(node r){
    	int i;
    	for(i=1;i<MAXSIZE;i++){
    		printf("%d\n",r.data[i]);
    	}
    	printf("----------------------");
    }
    //直接插入排序的函数使用 
    void sort(node r,int n){
    	int i,j;
    	int sortComp=0;
    	int sortMove=0;
    	for(i=2;i<n;i++){
    		r.data[0]=r.data[i];
    		sortMove++;
    		j=i-1;
    		while(sortComp++,r.data[j]>r.data[0]){
    			r.data[j+1]=r.data[j];
    			sortMove++;
    			j--;
    		}
    		r.data[j+1]=r.data[0];
    		sortMove++;
    	}
    //	for(i=1;i<MAXSIZE;i++){
    //		printf("%d\n",r.data[i]);
    //	}
    	printf("直接插入排序比较次数:%d\n",sortComp);
    	printf("直接插入排序移动次数:%d\n",sortMove);
    //	printf("\n");
    }
    //二分插入排序的函数使用 
    void binasort(node r,int n){
    	int i,j,l,h,mid;
    	int binaComp=0;
    	int binaMove=0;
    	for(i=2;i<n;i++){
    		r.data[0]=r.data[i];
    		l=1;
    		h=i-1;
    		while(l<=h){
    			mid =(l+h)/2;
    			if(r.data[0]<r.data[mid]){
    				h=mid-1;
    			}else{
    				l=mid+1;
    			}
    			binaComp++;
    		}
    		for(j=i-1;j>=l;j--){
    			r.data[j+1]=r.data[j];
    			binaMove++;
    		}
    		r.data[l]=r.data[0];
    		binaMove++;
    	}
    //	for(i=1;i<MAXSIZE;i++){
    //		printf("%d\n",r.data[i]);
    //	}
    //	printf("----------------------");
    	printf("二分插入排序比较次数:%d\n",binaComp);
    	printf("二分插入排序移动次数:%d\n",binaMove);
    //	printf("\n");
    }
    //冒泡排序的函数使用 
    void bubblesort(node r,int n){
    	int i=1,tag,j;
    	int bubbleComp=0;
    	int bubbleMove=0;
    	node x;
    	do{
    		tag=0;
    		for(j=n;j>i;j--){
    			bubbleComp++;
    			if(r.data[j]<r.data[j-1]){
    			x.data[0]=r.data[j];
    			r.data[j]=r.data[j-1];
    			r.data[j-1]=x.data[0];
    			tag=1;
    			bubbleMove+=3;	
    			}
    		}
    		i++;
    	}while(tag == 1 && i<=n);
    //	for(i=1;i<MAXSIZE;i++){
    //		printf("%d\n",r.data[i]);
    //	}
    //	printf("---------------7-------");
    	printf("冒泡排序比较次数:%d\n",bubbleComp);
    	printf("冒泡插入排序移动次数:%d\n",bubbleMove);
    //	printf("\n");
    }
    //简单插入排序的函数使用 
    void sisort(node r,int n){
    	int i,j,z;
    	node x;
    	int sisortComp=0;
    	int sisortMove=0;
    	for(i=1;i<n;i++){
    		z=i;
    		for(j=i+1;j<=n;j++){
    			if(sisortComp++,r.data[j]<r.data[z]){
    				z=j;
    			}
    		}
    		if(z!=i){
    			x.data[0]=r.data[i];
    			r.data[i]=r.data[z];
    			r.data[z]=x.data[0];
    			sisortMove+=3;
    		}
    	}
    //	for(i=1;i<MAXSIZE;i++){
    //		printf("%d\n",r.data[i]);
    //	}
    	printf("简单选择排序比较次数:%d\n",sisortComp);
    	printf("简单选择排序移动次数:%d\n",sisortMove);
    //	printf("\n");
    }
    int main(){
    	node r;
    	putNumjiang(&r);
    //	shuchu(r);
    	double s=clock();
    	sort(r,2000);
    	double e=clock();
    	printf("直接插入排序的时间为 %lf ms\n",e-s); 
    	printf("------------------------------\n");
    	s=clock();
    	binasort(r,2000);
    	e=clock();
    	printf("二分插入排序的时间为%lf ms\n",e-s);
    	printf("------------------------------\n");
    	s=clock();
    	bubblesort(r,2000);
    	e=clock();
    	printf("冒泡排序的时间为%lf ms\n",e-s);
    	printf("------------------------------\n");
    	s=clock();
    	sisort(r,2000); 
    	e=clock();
    	printf("简单选择排序的时间为%lf ms",e-s);
    }
    

    实验步骤与算法描述
    1.实验开始时,创建顺序表结构体;
    2.初始化顺序表结构体,并且选择升序、降序、无序;
    3.升序版本,for循环往顺序表添加数组的数据,每循环一次数据+1;
    4.降序版本,for循环往顺序表添加数组的数据,每循环一次数据-1;
    5.无序版本,使用srand(time(0))函数生成一个种子,保证数组中的数字都是不重复的。
    6.设置double s=clock(),之后进行直接插入函数的(升序/降序/无序)排列,在函数中设置对比次数和移动次数,结束后设置double e=clock(),输出e-s得到直接插入函数的时间。
    7.设置 s=clock(),之后进行折半插入排序的(升序/降序/无序)排列,在函数中设置对比次数和移动次数,结束后设置 e=clock(),输出e-s得到折半插入排序函数的时间。
    8.设置s=clock(),之后进行冒泡排序函数的(升序/降序/无序)排列,在函数中设置对比次数和移动次数,结束后设置 e=clock(),输出e-s得到冒泡排序函数的时间。
    9.设置 s=clock(),之后进行简单选择排序函数的(升序/降序/无序)排列,在函数中设置对比次数和移动次数,结束后设置 e=clock(),输出e-s得到简单选择排序函数的时间。
    10.输出所有结果。

    这里举例一下直接插入排序的实验流程图,各个的代码可能不太一样,按照实际代码更改。
    直接插入排序
    4种算法在三种情况测试下的实验结果(比较次数、移动次数和运行耗时):
    从小到大:
    从小到大
    从大到小:
    从大到小
    随机产生:
    乱序版本
    算法性能的比较
    算法比较
    算法的改进意见
    直接插入排序算法:将搜索和数据移动这二个步骤合并。每次a[i]先和前面一个数据a[i-1]比较,如果a[i] > a[i-1]说明a[1]到a[i]也是有序的,无须调整。否则就令j=i-1,x(标记)=a[i]。然后一边将数据a[j]向后移动一边向前搜索,当有数据a[j]<a[i]时停止并将x放到a[j + 1]处。
    折半插入排序算法:当待排序列已是最佳次序时,只要将本次记录与有序序列的最后一个记录(即本次记录的前一个记录)比较,便可以结束本轮排序,无需进行后续运算。
    冒泡排序算法:若发现从某个位置x开始,不再进行记录交换,就说明r[i+1]到r[n-1]已经排好序,因此下一趟比较只要进行到位置x就行。冒泡算法改进,用变量x记录数据最后一次交换位置,下次再从x开始比较就可以了。

    展开全文
  • 1.实验目的 掌握内排序,比较各种排序的优、缺点。 2 需求分析 2.1原理 ...以上的排序算法均采用书中所用的算法。程序采用输入的时候仅输入所要的个数,具体的输入数据由程序随机产生个数,并且输出。
  • 数据结构 实验名称 常用的内部排序算法 作者 育人 一实验目的 掌握常见的内部排序算法的思想及其适用条件 掌握常见的内部排序算法的程序实现 二实验内容及要求 任务描述 1任务设计一个内部排序算法模拟系统利用该...
  • 深入浅出排序算法的多语言实现 作者:白宁超 2015年10月8日20:08:11 摘要:十一假期于实验室无趣,逐研究起数据结构之排序。...本文介绍常用的排序算法,主要从以下个方面:算法的介绍、算法思想、算...

    深入浅出排序算法的多语言实现

    作者:白宁超

    2015年10月8日20:08:11

    摘要:十一假期于实验室无趣,逐研究起数据结构之排序。起初觉得就那么几种排序,两三天就搞定了,后来随着研究的深入,发觉里面有不少东西。本文介绍常用的排序算法,主要从以下几个方面:算法的介绍、算法思想、算法步骤、算法优缺点、算法实现、运行结果、算法优化等。最后对本文进行总结。本文为作者原创,程序经测试无误。部分资料引用论文和网络材料以及博客,后续参见参考文献。(本文原创,转载注明出处:深入浅出排序算法的多语言实现

     1 排序的基本概念


    排序: 所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来。其确切定义如下:   

    输入:n个记录R1,R2,…,Rn,其相应的关键字分别为K1,K2,…,Kn。   

    输出:Ril,Ri2,…,Rin,使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。

    排序的稳定性:当待排序记录的关键字均不相同时,排序结果是惟一的,否则排序结果不唯一。在待排序的文件中,若存在多个关键字相同的记录,经过排序后这些具有相同关键字的记录之间的相对次序保持不变,该排序方法是稳定的;若具有相同关键字的记录之间的相对次序发生变化,则称这种排序方法是不稳定的。  

    注意: 排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中,只要有一个实例使得算法不满足稳定性要求,则该排序算法就是不稳定的。

    排序方法的分类:

    1.按是否涉及数据的内、外存交换分

         在排序过程中,若整个文件都是放在内存中处理,排序时不涉及数据的内、外存交换,则称之为内部排序(简称内排序);反之,若排序过程中要进行数据的内、外存交换,则称之为外部排序。

    注意:  ① 内排序适用于记录个数不很多的小文件  ② 外排序则适用于记录个数太多,不能一次将其全部记录放人内存的大文件。

    2.按策略划分内部排序方法

         可以分为五类:插入排序、选择排序、交换排序、归并排序和分配排序。

    排序算法分析

    1.排序算法的基本操作 :   

    (1) 比较两个关键字的大小;   

    (2) 改变指向记录的指针或移动记录本身。  

    注意:第(2)种基本操作的实现依赖于待排序记录的存储方式。

    2.待排文件的常用存储方式

    (1) 以顺序表(或直接用向量)作为存储结构    

    排序过程:对记录本身进行物理重排(即通过关键字之间的比较判定,将记录移到合适的位置)

    (2) 以链表作为存储结构   

    排序过程:无须移动记录,仅需修改指针。通常将这类排序称为链表(或链式)排序;

    (3) 用顺序的方式存储待排序的记录,但同时建立一个辅助表(如包括关键字和指向记录位置的指针组成的索引表)   

    排序过程:只需对辅助表的表目进行物理重排(即只移动辅助表的表目,而不移动记录本身)。适用于难于在链表上实现,仍需避免排序过程中移动记录的排序方法。

    3.排序算法性能评价

    (1) 评价排序算法好坏的标准   

    ① 执行时间和所需的辅助空间      ② 算法本身的复杂程度

    (2) 排序算法的空间复杂度   

    若排序算法所需的辅助空间并不依赖于问题的规模n,即辅助空间是O(1),则称之为就地排序(In-PlaceSou)。   非就地排序一般要求的辅助空间为O(n)。

    (3) 排序算法的时间开销   

    大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模,还取决于输入实例中数据的状态。

    文件的顺序存储结构表示

    #define n l00 //假设的文件长度,即待排序的记录数目
      typedef int KeyType; //假设的关键字类型
      typedef struct{ //记录类型
        KeyType key; //关键字项
        InfoType otherinfo;//其它数据项,类型InfoType依赖于具体应用而定义
       }RecType;
      typedef RecType SeqList[n+1];//SeqList为顺序表类型,表中第0个单元一般用作哨兵

     

    2 交换排序


    交换排序的基本思想是:两两比较待排序记录的关键字,发现两个记录的次序相反时即进行交换,直到没有反序的记录为止。
    应用交换排序基本思想的主要排序方法有:冒泡排序和快速排序。

    2.1 冒泡排序

    冒泡排序:一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

    算法步骤:

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

    2)对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

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

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

    排序算法特点,算法复杂度

    时间复杂度为O(n^2),虽然不及堆排序、快速排序的O(nlogn,底数为2),但是有两个优点:1.“编程复杂度”很低,很容易写出代码;2.具有稳定性。

    其中若记录序列的初始状态为"正序",则冒泡排序过程只需进行一趟排序,在排序过程中只需进行n-1次比较,且不移动记录;反之,若记录序列的初始状态为"逆序",则需进行n(n-1)/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。

    冒泡排序示意图:

    冒泡排序示意图

     

    数据结构算法的实现:

    void BubbleSort(SeqList R)
       { //R(l..n)是待排序的文件,采用自下向上扫描,对R做冒泡排序
         int i,j;
         Boolean exchange; //交换标志
         for(i=1;i<n;i++){ //最多做n-1趟排序
           exchange=FALSE; //本趟排序开始前,交换标志应为假
           for(j=n-1;j>=i;j--) //对当前无序区R[i..n]自下向上扫描
            if(R[j+1].key<R[j].key){//交换记录
              R[0]=R[j+1]; //R[0]不是哨兵,仅做暂存单元
              R[j+1]=R[j];
              R[j]=R[0];
              exchange=TRUE; //发生了交换,故将交换标志置为真
             }
           if(!exchange) //本趟排序未发生交换,提前终止算法
                 return;
         } //endfor(外循环)
        } //BubbleSort

     

    排序算法的java实现

    package com.multiplesort.bnc;
    
    import java.util.Arrays;
    
    /**
     * 各种排序算法分析比较之冒泡排序:【交换排序】
     * @author bnc
     * @see    http://www.cnblogs.com/liuling/p/2013-7-24-01.html
     */
    public class BubbleSort {
        
        /**
         * 随机生成从0-n的随机数组
         * @param n  数组的成都
         * @return resultArr   数组
         * @author 白宁超
         */
        public static int[] randomArray(int arrayLength,int maxNum){
            int[] array=new int[arrayLength];
            for(int i=0;i<array.length;i++){
                array[i]=(int)(Math.random()*maxNum);
            }
            return array;
        }
        /**
         * 数据交换
         * @param data  整数型数组
         * @param i     第一层循环指针
         * @param j     第二层循环指针
         */
        private static void swap(int[] data, int i, int j) { 
            int temp=data[i];
            data[i]=data[j];
            data[j]=temp;
        }
        /**
         * 简单的冒泡排序:稳定
         * @deprecated :冒泡排序是一种稳定的排序方法。 
              •若文件初状为正序,则一趟起泡就可完成排序,排序码的比较次数为n-1,且没有记录移动,时间复杂度是O(n)
              •若文件初态为逆序,则需要n-1趟起泡,每趟进行n-i次排序码的比较,且每次比较都移动三次,比较和移动次数均达到最大值∶O(n^2)
              •起泡排序平均时间复杂度为O(n^2)
         * @param data 整数数组
          */
        public static void BubbleSort0(int[] array){
            int i,j;
            for(i=0;i<array.length;i++){
                for(j=i+1;j<array.length;j++){
                    if(array[i]>array[j])
                        swap(array,i,j);//数据交换
                }
            }
            System.out.println();
            System.out.println("简单【冒泡排序】后的结果:");
             for (i = 0; i < array.length; i++) {
                 System.out.print(array[i]+" ");
             }
        }
        /**
         * 改进后的冒泡排序:稳定
         * @deprecated :冒泡排序是一种稳定的排序方法。 
              •若文件初状为正序,则一趟起泡就可完成排序,排序码的比较次数为n-1,且没有记录移动,时间复杂度是O(n)
              •若文件初态为逆序,则需要n-1趟起泡,每趟进行n-i次排序码的比较,且每次比较都移动三次,比较和移动次数均达到最大值∶O(n^2)
              •起泡排序平均时间复杂度为O(n^2)
         * @param data 整数数组
          */
        public static void BubbleSort1(int[] array){
            int i,j;
            for(i=0;i<array.length;i++){
                for(j=array.length-2;j>=i;j--){
                    if(array[j]>array[j+1]){
                    //    System.out.println(array[j]+"<--->"+array[j+1]);//测试结果前面排序影响后面,相当于是从缓存有序的数组中获取
                        swap(array,j,j+1);//数据交换
                    }
                }
            }
            System.out.println();
            System.out.println("改进后【冒泡排序】的结果:");
             for (i = 0; i < array.length; i++) {
                 System.out.print(array[i]+" ");
             }
        }
        /**
         * 当数组基本有序时,如何改进排序算法
         * @param array
         */
        public static void BubbleSort2(int[] array){
            int i,j;
            Boolean flag=true;
            for(i=0;i<array.length&&flag;i++){//如果flag为flag退出循环
                flag=false;
                for(j=array.length-2;j>=i;j--){
                    if(array[j]>array[j+1]){
                        swap(array,j,j+1);//数据交换
                        //System.out.println(array[j]+"<--->"+array[j+1]);
                        flag=true;//如果有数据交换,则flag为true
                    }
                }
            }
            System.out.println();
            System.out.println("基本有序数组【冒泡排序】的结果:");
             for (i = 0; i < array.length; i++) {
                 System.out.print(array[i]+" ");
             }
        }
        public static void main(String[] args) {
            int[] array=randomArray(20, 100);//随机生成0--100的20个长度的数组
            int[] array1={1,3,2,4,5,6};//基本有序数组
            
            System.out.println("冒泡排序前:");
            for(int i=0;i<array.length;i++){
                System.out.print(array[i]+" ");
            }
            System.out.println();
            System.out.println("使用内部排序的结果:");
            for(int i=0;i<array.length;i++){
                //使用内部排序的结果
                Arrays.sort(array);//内部排序
                System.out.print(array[i]+" ");
            }
            //BubbleSort0(array);
            //BubbleSort1(array);
            BubbleSort2(array1);
            
        }
    
    }
    View Code

     

    排序算法的phthon实现

    def bubble_sort(lists):
        # 冒泡排序
        count = len(lists)
        for i in range(0, count):
            for j in range(i + 1, count):
                if lists[i] > lists[j]:
                    lists[i], lists[j] = lists[j], lists[i]
        return lists

     

    2.2 快速排序

    快速排序:是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

    快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。

    算法步骤:

    1 从数列中挑出一个元素,称为 “基准”(pivot),

    2 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

    3 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

    递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

    快速排序示意图:

    快速排序示意图

    数据结构算法的实现:

    void QuickSort(SeqList R,int low,int high)
       { //对R[low..high]快速排序
         int pivotpos; //划分后的基准记录的位置
         if(low<high){//仅当区间长度大于1时才须排序
            pivotpos=Partition(R,low,high); //对R[low..high]做划分
            QuickSort(R,low,pivotpos-1); //对左区间递归排序
            QuickSort(R,pivotpos+1,high); //对右区间递归排序
          }
        } //QuickSort

     

    排序算法的java实现

    package com.multiplesort.bnc;
    /**
     * 快速排序
     * 基本思想:选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,
     *        此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
     * 分析:
                 快速排序是不稳定的排序。
                 快速排序的时间复杂度为O(nlogn)。
                  当n较大时使用快排比较好,当序列基本有序时用快排反而不好。
     * @author bnc
     *
     */
    public class QuickSort {
        //随机生成数组
        public static int[] randomArray(int arrayLength,int maxNum){
            int[] array=new int[arrayLength];
            for(int i=0;i<array.length;i++){
                array[i]=(int)(Math.random()*maxNum);
            }
            return array;
        }
        //数据交换
        public static void swap(int[] data,int i,int j){
            int temp=data[i];
            data[i]=data[j];
            data[j]=temp;
        }
        //打印出数组
        public static void printArray(int[] array){
            for(int i=0;i<array.length;i++){
                System.out.print(array[i]+" ");
            }
            System.out.println();
        }
        
        
        private static void quickSort(int[] array, int low, int high) {
            if(array.length>0)
            {
                if(low<high){ //如果不加这个判断递归会无法退出导致堆栈溢出异常
                    int middle = getMiddle(array,low,high);
                    quickSort(array, 0, middle-1);
                    quickSort(array, middle+1, high);
                }
            }
        }
    
        private static int getMiddle(int[] array, int low, int high) {
            //int m=low+(high-low)/2;//计算数组元素中间的下标
            int temp = array[low];//基准元素
            while(low<high){
                //找到比基准元素小的元素位置
                while(low<high && array[high]>=temp){
                    high--;
                }
                array[low] = array[high]; 
                while(low<high && array[low]<=temp){
                    low++;
                }
                array[high] = array[low];
            }
            array[low] = temp;
            return low;
        }
    
        //快排
        public static void quickSort(int[] array){
            System.out.println("快速排序前的结果");
            printArray(array);
            
            quickSort(array,0,array.length-1);
    
            System.out.println("快速排序后的结果");
            printArray(array);
        }
        
        public static void main(String[] args) {
            quickSort(randomArray(20, 100));
        }
    
    }
    View Code

     

    排序算法的phthon实现

    def quick_sort(lists, left, right):
        # 快速排序
        if left >= right:
            return lists
        key = lists[left]
        low = left
        high = right
        while left < right:
            while left < right and lists[right] >= key:
                right -= 1
            lists[left] = lists[right]
            while left < right and lists[left] <= key:
                left += 1
            lists[right] = lists[left]
        lists[right] = key
        quick_sort(lists, low, left - 1)
        quick_sort(lists, left + 1, high)
        return lists

     

    3 选择排序


    3.1 直接选择排序

    选择排序(Selection sort)也是一种简单直观的排序算法。

    算法步骤:

    1)首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置

    2)再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。

    3)重复第二步,直到所有元素均排序完毕。

    排序算法特点,算法复杂度

    选择排序的交换操作介于0和(n-1)次之间。选择排序的比较操作为n(n-1)/2次之间。选择排序的赋值操作介于0和3(n-1)次之间。

    比较次数O(n^2),比较次数与关键字的初始状态无关,总的比较次数N=(n-1)+(n-2)+...+1=n*(n-1)/2。 交换次数O(n),最好情况是,已经有序,交换0次;最坏情况是,逆序,交换n-1次。 交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CPU时间多,n值较小时,选择排序比冒泡排序快。

    直接选择排序示意图:

    选择排序示意图

    数据结构算法的实现:

    void SelectSort(SeqList R)
     {
       int i,j,k;
       for(i=1;i<n;i++){//做第i趟排序(1≤i≤n-1)
         k=i;
         for(j=i+1;j<=n;j++) //在当前无序区R[i..n]中选key最小的记录R[k]
           if(R[j].key<R[k].key)
             k=j; //k记下目前找到的最小关键字所在的位置
           if(k!=i){ //交换R[i]和R[k]
             R[0]=R[i];R[i]=R[k];R[k]=R[0]; //R[0]作暂存单元
            } //endif
         } //endfor
      } //SeleetSort

     

    排序算法的java实现

    package com.multiplesort.bnc;
    
    
    /**
     * 选择排序:简单选择排序、堆排序。
     * 思想:每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置,直到全部排完。
     * 关键问题:在剩余的待排序记录序列中找到最小关键码记录。
     * •方法:
              –直接选择排序
              –堆排序
     * @author bnc
     *
     */
    public class SimpleSelectionSort {
        //随机生成一组数
        public static int[]  randomArray(int arrayLength,int maxNum){
            int[] array=new int[arrayLength];
            for(int i=0;i<array.length;i++){
                array[i]=(int)(Math.random()*maxNum);
            }
            return array;
        }
        //数据交换
        public static void swap(int[] data,int i,int j){
            int temp=data[i];
            data[i]=data[j];
            data[j]=temp;
        }
        //打印出数组
        public static void printArray(int[] array){
            for(int i=0;i<array.length;i++){
                System.out.print(array[i]+" ");
            }
            System.out.println();
        }
        ////简单的选择排序:
        //基本思想:在要排序的一组数中,选出最小的一个数与第一个位置的数交换;然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。
        public static void simpleSeclectSort(int[] array){
            int i,j,min;
            for(i=0;i<array.length;i++){
                min=i;  //将当前下标定义最小下标
                for(j=i+1;j<array.length;j++){ //循环之后的数据
                    if(array[min]>array[j])  //如果有小于当前值的最小数据
                        min=j;                //关键字的最小下标赋值给min
                }
                if(i!=min){               //若min!=i,说明找到最小值交换
                    swap(array,i,min);    //最小的一个数与第i位置的数交换
                }
            }
            System.out.println("排序后的数组:");
            printArray(array);
        }
        ////简单的选择排序:
        //基本思想:在要排序的一组数中,选出最小的一个数与第一个位置的数交换;然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止。
        public static void simpleSeclectSort1(int[] array){
            int i,j,min;
            for(i=0;i<array.length;i++){
                min=array[i];
                int n=i;//将当前下标定义最小下标
                for(j=i+1;j<array.length;j++){ //循环之后的数据
                    if(min>array[j]){  //如果有小于当前值的最小数据
                        min=array[j];
                        n=j;            //关键字的最小下标赋值给min
                    }
                }
                array[n]=array[i];
                array[i]=min;
            }
            System.out.println("排序后的数组:");
            printArray(array);
        }
        public static void main(String[] args) {
            int[] array=randomArray(10, 100);
            System.out.println("排序前的数组:");
            printArray(array);
            simpleSeclectSort1(array);
    
        }
    
    }
    View Code

     

    排序算法的phthon实现

    def select_sort(lists):
        # 选择排序
        count = len(lists)
        for i in range(0, count):
            min = i
            for j in range(i + 1, count):
                if lists[min] > lists[j]:
                    min = j
            lists[min], lists[i] = lists[i], lists[min]
        return lists

     

    3.2 堆排序

    堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

    堆排序的平均时间复杂度为Ο(nlogn) 。

    算法步骤:

    1)创建一个堆H[0..n-1]

    2)把堆首(最大值)和堆尾互换

    3)把堆的尺寸缩小1,并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置

    4) 重复步骤2,直到堆的尺寸为1

    排序算法特点,算法复杂度

    堆排序的平均时间复杂度为(nlogn),空间复杂度为O(1)

    由于它在直接选择排序的基础上利用了比较结果形成。效率提高很大。它完成排序的总比较次数为O(nlog2n)。它是对数据的有序性不敏感的一种算法。但堆排序将需要做两个步骤:-是建堆,二是排序(调整堆)。所以一般在小规模的序列中不合适,但对于较大的序列,将表现出优越的性能。

    堆排序示意图:

    堆排序示意图

    数据结构算法的实现:

    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

     

    排序算法的java实现

    package com.multiplesort.bnc;
    
    import java.util.Arrays;
    
    /**
     * 选择排序:堆排序
     * 适用于大数据
     * 稳定性:不稳定
     * 堆排序是一种树形选择排序,是对直接选择排序的有效改进。
     * 堆的定义下:具有n个元素的序列 (h1,h2,...,hn),当且仅当满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1) (i=1,2,...,n/2)时称之为堆。
     *         在这里只讨论满足前者条件的堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项(大顶堆)。完全二 叉树可以很直观地表示堆的结构。堆顶为根,其它为左子树、右子树。
     * 思想:初始时把要排序的数的序列看作是一棵顺序存储的二叉树,调整它们的存储序,使之成为一个 堆,这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。
     *    然后对前面(n-1)个数重新调整使之成为堆。依此类推,直到只有两个节点的堆,并对 它们作交换,最后得到有n个节点的有序序列。
     *    从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。
     * 初始序列:50,10,90,30,70,40,80,60,20
     * @author bnc
     *
     */
    public class HeapSort {
    
       //随机生成一组数
        public static int[]  randomArray(int arrayLength,int maxNum){
            int[] array=new int[arrayLength];
            for(int i=0;i<array.length;i++){
                array[i]=(int)(Math.random()*maxNum);
            }
            return array;
        }
        //数据交换
        public static void swap(int[] data,int i,int j){
            int temp=data[i];
            data[i]=data[j];
            data[j]=temp;
        }
        //打印出数组
        public static void printArray(int[] array){
            for(int i=0;i<array.length;i++){
                System.out.print(array[i]+" ");
            }
            System.out.println();
        }
        
        /**
         *构建大顶堆 
         * @param array 待建堆的数据
         * @param lastIndex    从lastIndex处节点(最后一个节点)的父节点开始
         */
        public static void buildMaxHeap(int[] array,int lastIndex){
             for(int i=(lastIndex-1)/2;i>=0;i--){
                 int k=i;  //k保存正在判断的节点 
                 while(k*2+1<=lastIndex){  //如果当前k节点的子节点存在  
                     int biggerIndex=2*k+1;  //k节点的左子节点的索引 
                     if(biggerIndex<lastIndex){  //如果biggerIndex小于lastIndex,即biggerIndex+1代表的k节点的右子节点存在
                         if(array[biggerIndex]<array[biggerIndex+1])  //若果右子节点的值较大  
                             biggerIndex++;  //biggerIndex总是记录较大子节点的索引  
                     }
                     if(array[k]<array[biggerIndex]){  //如果k节点的值小于其较大的子节点的值  
                         swap(array,k,biggerIndex);  
                         k=biggerIndex; //将biggerIndex赋予k,开始while循环的下一次循环,重新保证k节点的值大于其左右子节点的
                     }
                     else 
                         break;  
                 }
             }
        }
    
        //堆排序
        public static void heapSort(int[] array){
            int arrayLength=array.length;
            //循环建堆  
            for(int i=0;i<arrayLength-1;i++){  
                 buildMaxHeap(array,arrayLength-1-i);  
                 //交换堆顶和最后一个元素
                 swap(array,0,arrayLength-1-i);  
            }
            printArray(array);
        }
        
        //建大堆
        public static void  HeapAdjust(int[] array,int s,int m){
            int temp,j;
            temp=array[s];
            for(j=(2*s+1);j<m;j=(j*2+1)){
                //System.out.println("j:"+j+" array[j]:"+array[j]);
                if(j<m-1&&array[j]<array[j+1])
                    ++j;
                if(temp>array[j])
                    break;
                array[s]=array[j];
                s=j;
            }
            array[s]=temp;
        }
        //堆排序
        public static void heapSort1(int[] array){
            int i,length;
            length=array.length;
            for(i=(length-1)/2;i>=0;i--)
                HeapAdjust(array,i,length);
            printArray(array);
            for(i=length;i>1;i--){
                swap(array,0,i-1);
                HeapAdjust(array,0,i-1);
            }
            printArray(array);
        }
        
        
        public static void main(String[] args) {
            int[] array={50,10,234,90,456,30,70,40,80,60,20,300,1000,1,30,1,45};
            //heapSort(randomArray(11, 100));
            
            int[] a = randomArray(15, 100);
            heapSort1(a);
        }
    
    }
    View Code

     

    排序算法的phthon实现

    # 调整堆
    def adjust_heap(lists, i, size):
        lchild = 2 * i + 1
        rchild = 2 * i + 2
        max = i
        if i < size / 2:
            if lchild < size and lists[lchild] > lists[max]:
                max = lchild
            if rchild < size and lists[rchild] > lists[max]:
                max = rchild
            if max != i:
                lists[max], lists[i] = lists[i], lists[max]
                adjust_heap(lists, max, size)
    # 创建堆
    def build_heap(lists, size):
        for i in range(0, (size/2))[::-1]:
            adjust_heap(lists, i, size)
    # 堆排序
    def heap_sort(lists):
        size = len(lists)
        build_heap(lists, size)
        for i in range(0, size)[::-1]:
            lists[0], lists[i] = lists[i], lists[0]
            adjust_heap(lists, 0, i)

     

    4 插入排序


    4.1 直接插入排序

    冒泡排序:一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

    算法步骤:

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

    2)对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

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

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

    排序算法特点,算法复杂度

    如果目标是把n个元素的序列升序排列,那么采用直接插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。直接插入排序的赋值操作是比较操作的次数减去(n-1)次。平均来说直接插入排序算法复杂度为O(n2)。因而,直接插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么直接插入排序还是一个不错的选择。 插入排序在工业级库中也有着广泛的应用,在STL的sort算法和stdlib的qsort算法中,都将插入排序作为快速排序的补充,用于少量元素的排序(通常为8个或以下)。

    插入排序示意图:

    插入排序示意图

    数据结构算法的实现:

    void lnsertSort(SeqList R)
       { //对顺序表R中的记录R[1..n]按递增序进行插入排序
        int i,j;
        for(i=2;i<=n;i++) //依次插入R[2],…,R[n]
          if(R[i].key<R[i-1].key){//若R[i].key大于等于有序区中所有的keys,则R[i]
                                  //应在原有位置上
            R[0]=R[i];j=i-1; //R[0]是哨兵,且是R[i]的副本
            do{ //从右向左在有序区R[1..i-1]中查找R[i]的插入位置
             R[j+1]=R[j]; //将关键字大于R[i].key的记录后移
             j-- ;
             }while(R[0].key<R[j].key); //当R[i].key≥R[j].key时终止
            R[j+1]=R[0]; //R[i]插入到正确的位置上
           }//endif
       }//InsertSort

     

    排序算法的java实现

    package com.multiplesort.bnc;
    /**
     * 插入排序:
     * 思想:每步将一个待排序的记录,按其顺序码大小插入到前面已经排序的字序列的合适位置,直到全部插入排序完为止。
     * 关键问题:在前面已经排好序的序列中找到合适的插入位置。
     * 优点:记录本身基本有序,记录数比较少。
     * 基本有序的定义:小的关键字基本在前面,大的基本在后面,不大不小基本在中间
     * @author bnc
     *
     */
    public class StraightInsertionSort {
    
        //随机生成数组
        public static int[] randomArray(int arrayLength,int maxNum){
            int[] array=new int[arrayLength];
            for(int i=0;i<array.length;i++){
                array[i]=(int)(Math.random()*maxNum);
            }
            return array;
        }
        //数据交换
        public static void swap(int[] data,int i,int j){
            int temp=data[i];
            data[i]=data[j];
            data[j]=temp;
        }
        //打印出数组
        public static void printArray(int[] array){
            for(int i=0;i<array.length;i++){
                System.out.print(array[i]+" ");
            }
            System.out.println();
        }
    
        /**
         * 直接插入排序(从后向前找到合适位置后插入)
         * 基本思想:每步将一个待排序的记录,按其顺序码大小插入到前面已经排序的字序列的合适位置(从后向前找到合适位置后),直到全部插入排序完为止。
         * 直接插入排序是稳定的排序。关于各种算法的稳定性分析可以参考http://www.cnblogs.com/Braveliu/archive/2013/01/15/2861201.html
         * 文件初态不同时,若文件初态为正序算法的时间复杂度为O(n),这时最好的情况。若初态为反序,则第i个待插入记录需要比较i+1次才能找到合适位置插入,故时间复杂度为O(n2),这时最坏的情况。
         * 直接插入排序的平均时间复杂度为O(n2)。
         * @param array
         */
        public static void insertSort(int[] array){
            System.out.println("直接插入排序前的结果");
            printArray(array);
            
            for(int i=1;i<array.length;i++){
                int temp=array[i];  //待插入的元素
                int j;
                for(j=i-1;j>=0;j--){
                    if(array[j]>temp) //将大于temp的元素右移 
                        array[j+1]=array[j];  //此时array[j+1]=array[j]=两者最大值
                    else
                        break;
                }
                array[j+1]=temp; //将待插入的元素赋值较小位置
            }
            
            System.out.println("直接插入排序后的结果");
            printArray(array);
        }
        
        
        public static void insertSort1(int[] array){
            System.out.println("直接插入排序前的结果");
            printArray(array);
            
            int i,j;
            for(i=1;i<array.length;i++){
               if(array[i]<array[i-1]){
                   int temp=array[i];  //设置哨兵
                   for(j=i-1;j>=0&&array[j]>=temp;j--){
                      
                       array[j+1]=array[j];  //记录后移
                   }
                   array[j+1]=temp;//插入正确位置
               }
            }
            
            System.out.println("直接插入排序后的结果");
            printArray(array);
        }
        public static void main(String[] args) {
            int[] array={57,68,59,52};
            insertSort(randomArray(10, 100));
            insertSort1(randomArray(10, 100));
        }
    
    }
    View Code

     

    排序算法的phthon实现

    def insert_sort(lists):
        # 插入排序
        count = len(lists)
        for i in range(1, count):
            key = lists[i]
            j = i - 1
            while j >= 0:
                if lists[j] > key:
                    lists[j + 1] = lists[j]
                    lists[j] = key
                j -= 1
        return lists

     

    4.2 希尔排序

    希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

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

    插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率 但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位 希尔排序的基本思想是:先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。

    算法步骤:

    1)选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;

    2)按增量序列个数k,对序列进行k 趟排序;

    3)每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

    排序算法特点,算法复杂度

    希尔排序是基于插入排序的一种算法, 在此算法基础之上增加了一个新的特性,提高了效率。希尔排序的时间复杂度为 O(N*(logN)2), 没有快速排序算法快  O(N*(logN)),因此中等大小规模表现良好,对规模非常大的数据排序不是最优选择。但是比O(N2)复杂度的算法快得多。并且希尔排序非常容易实现,算法代码短而简单。 此外,希尔算法在最坏的情况下和平均情况下执行效率相差不是很多,与此同时快速排序在最坏 的情况下执行的效率会非常差。专家们提倡,几乎任何排序工作在开始时都可以用希尔排序,若在实际使用中证明它不够快, 再改成快速排序这样更高级的排序算法.

    希尔排序是按照不同步长对元素进行插入排序,当刚开始元素很无序的时候,步长最大,所以插入排序的元素个数很少,速度很快;当元素基本有序了,步长很小,插入排序对于有序的序列效率很高。所以,希尔排序的时间复杂度会比o(n^2)好一些。由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以shell排序是不稳定的

    希尔排序示意图:

    希尔排序示意图

    数据结构算法的实现:

    void ShellPass(SeqList R,int d)
       {//希尔排序中的一趟排序,d为当前增量
         for(i=d+1;i<=n;i++) //将R[d+1..n]分别插入各组当前的有序区
           if(R[i].key<R[i-d].key){
             R[0]=R[i];j=i-d; //R[0]只是暂存单元,不是哨兵
             do {//查找R[i]的插入位置
                R[j+d];=R[j]; //后移记录
                j=j-d; //查找前一记录
             }while(j>0&&R[0].key<R[j].key);
             R[j+d]=R[0]; //插入R[i]到正确的位置上
           } //endif
       } //ShellPass
    
      void  ShellSort(SeqList R)
       {
        int increment=n; //增量初值,不妨设n>0
        do {
              increment=increment/3+1//求下一增量
              ShellPass(R,increment); //一趟增量为increment的Shell插入排序
           }while(increment>1)
        } //ShellSort

     

    排序算法的java实现

    package com.multiplesort.bnc;
    /**
     * 希尔排序
     * 基本思想:先取一个小于n的整数d1作为第一个增量,把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;
     *       然后,取第二个增量d2<d1重复上述的分组和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。
     * 我们知道一次插入排序是稳定的,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以希尔排序是不稳定的。
     * 希尔排序的时间性能优于直接插入排序,原因如下:
      (1)当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
      (2)当n值较小时,n和n2的差别也较小,即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。
      (3)在希尔排序开始时增量较大,分组较多,每组的记录数目少,故各组内直接插入较快,后来增量di逐渐缩小,分组数逐渐减少,而各组的记录数目逐渐增多,
                     但由于已经按di-1作为距离排过序,使文件较接近于有序状态,所以新的一趟排序过程也较快。
               因此,希尔排序在效率上较直接插人排序有较大的改进。
     * 希尔排序的平均时间复杂度为O(nlogn)。
     * @author bnc
     *
     */
    public class ShellSort {
    
        //随机生成数组
        public static int[] randomArray(int arrayLength,int maxNum){
            int[] array=new int[arrayLength];
            for(int i=0;i<array.length;i++){
                array[i]=(int)(Math.random()*maxNum);
            }
            return array;
        }
        //数据交换
        public static void swap(int[] data,int i,int j){
            int temp=data[i];
            data[i]=data[j];
            data[j]=temp;
        }
        //打印出数组
        public static void printArray(int[] array){
            for(int i=0;i<array.length;i++){
                System.out.print(array[i]+" ");
            }
            System.out.println();
        }
            
        //希尔排序
        public static void shellSort(int[] array){
            System.out.println("希尔排序前的结果");
            printArray(array);
            
            
            int d=array.length;  //步长
            while(true){
                d=d/2;
                for(int x=0;x<d;x++){
                    for(int i=x+d;i<array.length;i+=d){
                        int temp=array[i];
                        int j;
                        for(j=i-d;j>=0&&array[j]>temp;j-=d){
                            array[j+d]=array[j];
                        }
                        array[j+d]=temp;
                    }
                }
                if(d==1)
                    break;
            }
            
            System.out.println("希尔排序后的结果");
            printArray(array);
        }
        //希尔排序
        public static void shellSort1(int[] array){
            System.out.println("希尔排序前的结果");
            printArray(array);
            
            
            int i,j;
            int increment=array.length;
            do{
                increment=increment/3+1;
                for(i=increment;i<array.length;i++){
                    if(array[i]<array[i-increment])
                    {
                        int temp=array[i];
                        for(j=i-increment;j>=0&&temp<array[j];j-=increment){
                            array[j+increment]=array[j];
                        }
                        array[j+increment]=temp;
                    }
                }
            }
            while(increment>1);
            
            System.out.println("希尔排序后的结果");
            printArray(array);
        }         
        public static void main(String[] args) {
            int[] a={9,1,5,8,3,7,4,6,2};
             //shellSort(randomArray(10, 100));
            shellSort1(randomArray(20, 100));
            //shellSort1(a);
        }
    
    }
    View Code

     

    排序算法的phthon实现

    def shell_sort(lists):
        # 希尔排序
        count = len(lists)
        step = 2
        group = count / step
        while group > 0:
            for i in range(0, group):
                j = i + group
                while j < count:
                    k = j - group
                    key = lists[j]
                    while k >= 0:
                        if lists[k] > key:
                            lists[k + group] = lists[k]
                            lists[k] = key
                        k -= group
                    j += group
            group /= step
        return lists

     

    5 归并排序


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

    算法步骤:

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

    2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置

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

    4. 重复步骤3直到某一指针达到序列尾

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

    快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

    排序算法特点,算法复杂度

    归并排序是一种非就地排序,将需要与待排序序列一样多的辅助空间。在使用它对两个己有序的序列归并,将有无比的优势。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。对数据的有序性不敏感。若数据节点数据量大,那将不适合。

    归并排序示意图:

    归并排序示意图

    数据结构算法的实现:

    void Merge(SeqList R,int low,int m,int high)
        {//将两个有序的子文件R[low..m)和R[m+1..high]归并成一个有序的
         //子文件R[low..high]
         int i=low,j=m+1,p=0//置初始值
         RecType *R1; //R1是局部向量,若p定义为此类型指针速度更快
         R1=(ReeType *)malloc((high-low+1)*sizeof(RecType));
         if(! R1) //申请空间失败
           Error("Insufficient memory available!");
         while(i<=m&&j<=high) //两子文件非空时取其小者输出到R1[p]上
           R1[p++]=(R[i].key<=R[j].key)?R[i++]:R[j++];
         while(i<=m) //若第1个子文件非空,则复制剩余记录到R1中
           R1[p++]=R[i++];
         while(j<=high) //若第2个子文件非空,则复制剩余记录到R1中
           R1[p++]=R[j++];
         for(p=0,i=low;i<=high;p++,i++)
           R[i]=R1[p];//归并完成后将结果复制回R[low..high]
        } //Merge

     

    排序算法的java实现

    package com.multiplesort.bnc;
    /**
     * 归并排序
     * 基本思想:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列
     * 分析:
                归并排序是稳定的排序方法。
                归并排序的时间复杂度为O(nlogn)。
                速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列。
     * @author bnc
     *
     */
    public class MergingSort {
    
        //随机生成数组
        public static int[] randomArray(int arrayLength,int maxNum){
            int[] array=new int[arrayLength];
            for(int i=0;i<array.length;i++){
                array[i]=(int)(Math.random()*maxNum);
            }
            return array;
        }
        //数据交换
        public static void swap(int[] data,int i,int j){
            int temp=data[i];
            data[i]=data[j];
            data[j]=temp;
        }
        //打印出数组
        public static void printArray(int[] array){
            for(int i=0;i<array.length;i++){
                System.out.print(array[i]+" ");
            }
            System.out.println();
        }
        //合并
        private static void merge(int[] array, int left, int middle, int right) {
            int[] tempArray=new int[array.length];
            int mid=middle+1;//右边起始位置
            int temp=left;
            int third=left;
            while(left<=middle&&mid<=right){
                //从两个数组中选取较小的数放入中间数组
                 if(array[left]<=array[mid]){
                       tempArray[third++] = array[left++];
                 }
                 else
                     tempArray[third++]=array[mid++];
            }
            //将剩余的部分放入中间数组
             while(left<=middle){
                 tempArray[third++] = array[left++];
             }
             while(mid<=right){
                 tempArray[third++] = array[mid++];
             }
            //将中间数组复制回原数组
             while(temp<=right){
                 array[temp] = tempArray[temp++];
             }
        }
        
        //归并排序
        private static void mergeSort(int[] array, int left, int right) {
            if(left<right){
                int middle=(left+right)/2;
                //对左边进行递归
                mergeSort(array, left, middle);
                //对右边进行递归
                mergeSort(array, middle+1, right);
                //合并
                merge(array,left,middle,right);
            }
        }
        //稳定,归并排序(二路归并)[递归]
        public static void mergingSort(int[] array){
            System.out.println("归并排序前的结果");
            printArray(array);
            
            //归并排序
            mergeSort(array,0,array.length-1);
            
            System.out.println("归并排序前的结果");
            printArray(array);
        }
        
        
        
        
        
        //两两归并
        public static void Merge(int[] SR,int[] TR,int i,int m,int n){
            int j,k,l;
            for(j=m+1,k=i;i<=m&&j<=n;k++){
                if(SR[i]<SR[j])
                    TR[k]=SR[i++];
                else
                    TR[k]=SR[j++];
            }
            if(i<=m){
                for(l=0;l<=m-i;l++)
                    TR[k+l]=SR[i+l];
            }
            if(j<=m){
                for(l=0;l<=n-j;l++)
                    TR[k+l]=SR[j+l];
            }
        }
        //归并
        public static void MergePass(int[] SR,int[] TR,int s,int n){
            int i=1;
            int j;
            while(i<=n-2*s-1){
                Merge(SR,TR,i,i+s-1,i+2*s-1);
                i=i+2*s;
            }
            if(i<n-s+1)
                Merge(SR, TR, i, i+s-1, n);
            else
                for(j=i;j<=n;j++)
                    TR[j]=SR[j];
        }
        //稳定,归并排序(二路归并)[非递归]
        public static void mergingSort1(int[] array){
            System.out.println("归并排序前的结果");
            printArray(array);
            
            int[] tempArray=new int[array.length+1];
            int k=0;
            while(k<array.length){
                MergePass(array,tempArray,k,array.length);
                k=2*k+1;
                MergePass(tempArray,array,k,array.length);
                k=2*k+1;
            }
            
            System.out.println("归并排序前的结果");
            printArray(array);
        }
        public static void main(String[] args) {
            int[] array={50,10,90,30,70,40,80,60,20};
            //mergingSort(randomArray(10, 100));
            //mergingSort(array);
            mergingSort1(array);
        }
    
    }
    View Code

     

    排序算法的phthon实现

    def merge(left, right):
        i, j = 0, 0
        result = []
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                result.append(left[i])
                i += 1
            else:
                result.append(right[j])
                j += 1
        result += left[i:]
        result += right[j:]
        return result
    def merge_sort(lists):
        # 归并排序
        if len(lists) <= 1:
            return lists
        num = len(lists) / 2
        left = merge_sort(lists[:num])
        right = merge_sort(lists[num:])
        return merge(left, right)

     

    6 分配排序


    6.1 箱排序

    箱排序也称桶排序(Bucket Sort),其基本思想是:设置若干个箱子,依次扫描待排序的记录R[0],R[1],…,R[n-1],把关键字等于k的记录全都装入到第k个箱子里(分配),然后按序号依次将各非空的箱子首尾连接起来(收集)。
    【例】要将一副混洗的52张扑克牌按点数A<2<…<J<Q<K排序,需设置13个"箱子",排序时依次将每张牌按点数放入相应的箱子里,然后依次将这些箱子首尾相接,就得到了按点数递增序排列的一副牌。

    数据结构算法的实现:

     伪代码算法为:
      void BucketSon(R)
        { //对R[0..n-1]做桶排序,其中0≤R[i].key<1(0≤i<n)
          for(i=0,i<n;i++) //分配过程.
            将R[i]插入到桶B[「n(R[i].key)」]中; //可插入表头上
          for(i=0;i<n;i++) //排序过程
            当B[i]非空时用插人排序将B[i]中的记录排序;
          for(i=0,i<n;i++) //收集过程
            若B[i]非空,则将B[i]中的记录依次输出到R中;
         }

     

    6.2 基数排序

    基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

    说基数排序之前,我们简单介绍桶排序:

    算法思想:是将阵列分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的阵列内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。 简单来说,就是把数据分组,放在一个个的桶中,然后对每个桶里面的在进行排序。

    例如要对大小为[1..1000]范围内的n个整数A[1..n]排序

    首先,可以把桶设为大小为10的范围,具体而言,设集合B[1]存储[1..10]的整数,集合B[2]存储   (10..20]的整数,……集合B[i]存储(   (i-1)*10,   i*10]的整数,i   =   1,2,..100。总共有  100个桶。

    然后,对A[1..n]从头到尾扫描一遍,把每个A[i]放入对应的桶B[j]中。  再对这100个桶中每个桶里的数字排序,这时可用冒泡,选择,乃至快排,一般来说任  何排序法都可以。

    最后,依次输出每个桶里面的数字,且每个桶中的数字从小到大输出,这  样就得到所有数字排好序的一个序列了。

    假设有n个数字,有m个桶,如果数字是平均分布的,则每个桶里面平均有n/m个数字。如果对每个桶中的数字采用快速排序,那么整个算法的复杂度是

    O(n   +   m   *   n/m*log(n/m))   =   O(n   +   nlogn   –   nlogm)

    从上式看出,当m接近n的时候,桶排序复杂度接近O(n)

    当然,以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的  ,实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中,那就退化成一般的排序了。

    前面说的几大排序算法 ,大部分时间复杂度都是O(n2),也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O(n)的时间复杂度。但桶排序的缺点是:

    1)首先是空间复杂度比较高,需要的额外开销大。排序有两个数组的空间开销,一个存放待排序数组,一个就是所谓的桶,比如待排序值是从0到m-1,那就需要m个桶,这个桶数组就要至少m个空间。

    2)其次待排序的元素都要在一定的范围内等等。

    排序算法的java实现

    package com.multiplesort.bnc;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * 基数排序
     * 基本思想:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
     * 基数排序是稳定的排序算法。
      基数排序的时间复杂度为O(d(n+r)),d为位数,r为基数。
     * @author bnc
     *
     */
    public class RadixSort {
        //随机生成数组
        public static int[] randomArray(int arrayLength,int maxNum){
            int[] array=new int[arrayLength];
            for(int i=0;i<array.length;i++){
                array[i]=(int)(Math.random()*maxNum);
            }
            return array;
        }
        //数据交换
        public static void swap(int[] data,int i,int j){
            int temp=data[i];
            data[i]=data[j];
            data[j]=temp;
        }
        //打印出数组
        public static void printArray(int[] array){
            for(int i=0;i<array.length;i++){
                System.out.print(array[i]+" ");
            }
            System.out.println();
        }
        
        //基数排序
        public static void radixSort(int[] array){
            System.out.println("基数排序前的结果");
            printArray(array);
            
             //找到最大数,确定要排序几趟
             int max = 0;
             for (int i = 0; i < array.length; i++) {
                 if(max<array[i])
                     max = array[i];
             }
             //判断位数
             int times = 0;
             while(max>0){
                 max = max/10;
                 times++;
             }
             //建立十个队列
              List<ArrayList> queue = new ArrayList<ArrayList>();
              for (int i = 0; i < 10; i++) {
                  ArrayList queue1 = new ArrayList();
                  queue.add(queue1);
              }
            //进行times次分配和收集
              for (int i = 0; i < times; i++) {
                //分配
                  for (int j = 0; j < array.length; j++) {
                      int x = array[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);
                      ArrayList queue2 = queue.get(x);
                      queue2.add(array[j]);
                      queue.set(x,queue2);
                  }
                //收集
                  int count = 0;
                  for (int j = 0; j < 10; j++) {
                      while(queue.get(j).size()>0){
                          ArrayList<Integer> queue3 = queue.get(j);
                          array[count] = queue3.get(0);
                          queue3.remove(0);
                          count++;
                      }
                  }
              }
            
            System.out.println("基数排序后的结果");
            printArray(array);
        }
        public static void main(String[] args) {
            radixSort(randomArray(10, 100));
    
        }
    
    }
    View Code

     

    排序算法的phthon实现

    import math
    def radix_sort(lists, radix=10):
        k = int(math.ceil(math.log(max(lists), radix)))
        bucket = [[] for i in range(radix)]
        for i in range(1, k+1):
            for j in lists:
                bucket[j/(radix**(i-1)) % (radix**i)].append(j)
            del lists[:]
            for z in bucket:
                lists += z
                del z[:]
        return lists

     

    7 总结


    各种排序方法比较

         简单排序中直接插入最好,快速排序最快,当文件为正序时,直接插入和冒泡均最佳。

    影响排序效果的因素

         因为不同的排序方法适应不同的应用环境和要求,所以选择合适的排序方法应综合考虑下列因素:  

    ①待排序的记录数目n;   ②记录的大小(规模);   ③关键字的结构及其初始状态;   

    ④对稳定性的要求;   ⑤语言工具的条件;   ⑥存储结构;   ⑦时间和辅助空间复杂度等。

    不同条件下,排序方法的选择

    (1)若n较小(如n≤50),可采用直接插入或直接选择排序。当记录规模较小时,直接插入排序较好;否则因为直接选择移动的记录数少于直接插人,应选直接选择排序为宜。

    (2)若文件初始状态基本有序(指正序),则应选用直接插人、冒泡或随机的快速排序为宜;

    (3)若n较大,则应采用时间复杂度为O(nlgn)的排序方法:快速排序、堆排序或归并排序。      

    快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;      

    堆排序所需的辅助空间少于快速排序,并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。      若要求排序稳定,则可选用归并排序。但本章介绍的从单个记录起进行两两归并的  排序算法并不值得提倡,通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件,然后再两两归并之。因为直接插入排序是稳定的,所以改进后的归并排序仍是稳定的。

    (4)在基于比较的排序方法中,每次比较两个关键字的大小之后,仅仅出现两种可能的转移,因此可以用一棵二叉树来描述比较判定过程。      

    (5)有的语言(如Fortran,Cobol或Basic等)没有提供指针及递归,导致实现归并、快速(它们用递归实现较简单)和基数(使用了指针)等排序算法变得复杂。此时可考虑用其它排序。

     排序对比:

     

    8 参考文献


    1. 大话数据结构(程杰)
    2. 排序算法可视化
    3. 数据结构自考网
    4. 排序算法汇总
    5. 各种排序算法的分析以及java实现

     

     

     

    转载于:https://my.oschina.net/u/3579120/blog/1539136

    展开全文
  • 在本科的时候,我们也学过数据结构与算法,内容比较多,还比较难,尤其是到了树的那三深度优先遍历和层次遍历,是核心也是难点,还有图的最短路径以及两最小生成树,以及最后的十大排序算法常用的查找,这些都...
  • 深入浅出排序算法的多语言实现 ... 摘要:十一假期于实验室无趣,逐...本文介绍常用的排序算法,主要从以下个方面:算法的介绍、算法思想、算法步骤、算法优缺点、算法实现、运行结果、算法优化等。最后对本文
  • 第7章和第8章讨论查找和排序,并介绍几种常用的查找和排序方法。第9章上机实验,给出4个完整的实例,并全部在VC++ 6.0环境下调试通过。  本书基础理论知识的阐述由浅入深、通俗易懂。各章节列举了很多实用的例子,...
  • 第7章和第8章讨论查找和排序,并介绍几种常用的查找和排序方法。第9章上机实验,给出4个完整的实例,并全部在VC++ 6.0环境下调试通过。 本书基础理论知识的阐述由浅入深、通俗易懂。各章节列举了很多实用的例子,有...
  • 第7章和第8章讨论查找和排序,并介绍几种常用的查找和排序方法。第9章上机实验,给出4个完整的实例,并全部在VC++ 6.0环境下调试通过。 本书基础理论知识的阐述由浅入深、通俗易懂。各章节列举了很多实用的例子,有...
  • 第7章和第8章讨论查找和排序,并介绍几种常用的查找和排序方法。第9章上机实验,给出4个完整的实例,并全部在VC++ 6.0环境下调试通过。 本书基础理论知识的阐述由浅入深、通俗易懂。各章节列举了很多实用的例子,有...
  • 全面论述排序、搜索、图处理和字符串处理的算法数据结构,涵盖每位程序员应知应会50种算法  全新修订代码 全新Java实现代码,采用模块化编程风格,所有代码均可供读者使用  与实际应用相结合 在重要...
  •  《算法(第4版)》全面讲述算法数据结构的必备知识,具有以下大特色。  1、 算法领域经典参考书:Sedgewick畅销著作*版,反映了经过十年演化而成的算法核心知识体系  2、内容全面:全面论述排序、搜索...
  • 具体讲述了二叉空间剖分(BSP)、八叉树等图形学中常用的数据结构。新版本增加了图形用户界面、椭圆、图像压缩和线条反走样算法等,还增加了Liang-Barsky裁剪算法和Nicholl-Lee- Nicholl裁剪算法。新版本大大扩充了可...
  • 《图灵程序设计丛书:算法(第4版)》全面讲述算法数据结构的必备知识,具有以下大特色: 算法领域经典参考书:Sedgewick畅销著作最新版,反映了经过十年演化而成的算法核心知识体系。 内容全面:全面论述...
  • 14 基于粒子群算法的PID控制优化算法(史峰) PID控制方法是工业领域中最常用的控制方法,然而在PID控制算法的使用中,P,I,D参数即比例 参数、积分参数、微分参数的确定是个难题,一般是凭经验获得。粒子群算法...
  • 数据结构里各种难啃“树”,一文搞懂它 一篇文章彻底学会递归思路解题! 哈希算法详解 计算机网络(TCP/IP协议栈) 计网 IP 知识全家桶,45 张图一套带走 ping命令用得这么6,原理知道不?图解一波! 探究:一...
  • 种需求,C++为每一种数据都提供了几种类型。本章将要讨论这些类型,包括创建变量和编写各种类型常 量。另外,还将讨论C抖是如何处理不同类型之间隐式和显式转换。 第4章:复合类型 C++允许程序员使用基本...
  • 种需求,C++为每一种数据都提供了几种类型。本章将要讨论这些类型,包括创建变量和编写各种类型常 量。另外,还将讨论C抖是如何处理不同类型之间隐式和显式转换。 第4章:复合类型 C++允许程序员使用基本...
  • 种需求,C++为每一种数据都提供了几种类型。本章将要讨论这些类型,包括创建变量和编写各种类型常 量。另外,还将讨论C抖是如何处理不同类型之间隐式和显式转换。 第4章:复合类型 C++允许程序员使用基本...
  • 种需求,C++为每一种数据都提供了几种类型。本章将要讨论这些类型,包括创建变量和编写各种类型常 量。另外,还将讨论C抖是如何处理不同类型之间隐式和显式转换。 第4章:复合类型 C++允许程序员使用基本...
  • OpenCV基础篇之Mat数据结构 OpenCV基础篇之像素访问 OpenCV基础篇之图片叠加 OpenCV基础篇之像素操作对比度调节 OpenCV基础篇之绘图及RNG随机数对象 OpenCV基础篇之查找表 OpenCV基础篇之图像频域 OpenCV图像处理篇...
  • 软件工程教程

    2012-07-06 23:10:29
    顺序图、协作图:单用例中个对象行为 顺序图突出顺序,协作图着重对象间链接关系 项目三 项目市场调研 任务1. 系统研发背景 任务2. 软件开发计划 油画创作背景 波洛克 《1948年第五号》 1.4亿$,最昂贵画作...
  • Marmir:把输入 Python 数据结构转换为电子表单。 openpyxl:一个用来读写 Excel 2010 xlsx/xlsm/xltx/xltm 文件库。 pyexcel:一个提供统一 API,用来读写,操作 Excel 文件库。 python-docx:读取,查询...
  • 4. 数据结构相关 红黑树结构,查找时间复杂度 堆排序的时间复杂度 Top K排序 如何用O(1)复杂度查找到stack里面最小值 八皇后 C++自己实现一个队列 数组和链表区别 什么是kd-tree,如何实现 青蛙跳台阶...

空空如也

空空如也

1 2
收藏数 33
精华内容 13
关键字:

数据结构几种常用的排序算法实验

数据结构 订阅