精华内容
下载资源
问答
  • 一、 实验目的1. 掌握各种常用排序的算法...交换类排序:如:冒泡排序,快速排序,其中冒泡排序应该是计算机专业的学生最为熟悉的一种排序算法了,而快速排序则是在冒泡排序的基础上一次消除多个逆序对改进而来3...

    一、 实验目的

    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;
    }



    展开全文
  • 各种排序方法的介绍与比较

    千次阅读 2018-12-31 14:08:22
    前记:这一章中主要对数据排序相关的概念和方法进行了讲解,今天的拓展资源就对排序的基本概念、几种常见排序方法的算法及优缺点、插入排序的算法和C语言实现等,同学们多了解一下。 排序:是计算机内经常进行的一...

    来源:我是码农,转载请保留出处和链接!

    本文链接:http://www.54manong.com/?id=210

    前记:这一章中主要对数据排序相关的概念和方法进行了讲解,今天的拓展资源就对排序的基本概念、几种常见排序方法的算法及优缺点、插入排序的算法和C语言实现等,同学们多了解一下。

    排序:是计算机内经常进行的一种操作,其目的是将一组“无序”的记录序列调整为“有序”的记录序列。

    内部排序:若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序;内部排序的过程是一个逐步扩大记录的有序序列长度的过程。

    外部排序:若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。

      内排序的方法有许多种,按所用策略不同,可归纳为五类:插入排序、选择排序、交换排序、归并排序和分配排序。

      其中,插入排序主要包括直接插入排序和希尔排序两种;选择排序主要包括直接选择排序和堆排序;交换排序主要包括气(冒)泡排序和快速排序。

    一、冒泡排序

      已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。首先比较a[1]与a[2]的值,若a[1]大于a[2]则交换两者的值,否则不变。再比较a[2]与a[3]的值,若a[2]大于a[3]则交换两者的值,否则不变。再比较a[3]与a[4],以此类推,最后比较a[n-1]与a[n]的值。这样处理一轮后,a[n]的值一定是这组数据中最大的。再对a[1]~a[n-1]以相同方法处理一轮,则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮,以此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。

    优点:稳定,比较次数已知;

    缺点:慢,每次只能移动相邻两个数据,移动数据的次数多。

    二、选择排序

      已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。首先比较a[1]与a[2]的值,若a[1]大于a[2]则交换两者的值,否则不变。再比较a[1]与a[3]的值,若a[1]大于a[3]则交换两者的值,否则不变。再比较a[1]与a[4],以此类推,最后比较a[1]与a[n]的值。这样处理一轮后,a[1]的值一定是这组数据中最小的。再将a[2]与a[3]~a[n]以相同方法比较一轮,则a[2]的值一定是a[2]~a[n]中最小的。再将a[3]与a[4]~a[n]以相同方法比较一轮,以此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。

    优点:稳定,比较次数与冒泡排序一样;

    缺点:相对之下还是慢。

    三、插入排序

      已知一组升序排列数据a[1]、a[2]、……a[n],一组无序数据b[1]、b[2]、……b[m],需将二者合并成一个升序数列。首先比较b[1]与a[1]的值,若b[1]大于a[1],则跳过,比较b[1]与a[2]的值,若b[1]仍然大于a[2],则继续跳过,直到b[1]小于a数组中某一数据a[x],则将a[x]~a[n]分别向后移动一位,将b[1]插入到原来a[x]的位置这就完成了b[1]的插入。b[2]~b[m]用相同方法插入。(若无数组a,可将b[1]当作n=1的数组a)

    优点:稳定,快;

    缺点:比较次数不一定,比较次数越少,插入点后的数据移动越多,特别是当数据总量庞大的时候,但用链表可以解决这个问题。

    四、缩小增量排序

      由希尔在1959年提出,又称希尔排序 (shell排序)。

      已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。发现当n不大时,插入排序的效果很好。首先取一增量d(d<n),将a[1]、a[1+d]、a[1+2d]……列为第一组,a[2]、a[2+d]、a[2+2d]……列为第二组……,a[d]、a[2d]、a[3d]……列为最后一组以次类推,在各组内用插入排序,然后取d'<d,重复上述操作,直到d=1。

    优点:快,数据移动少;

    缺点:不稳定,d的取值是多少,应取多少个不同的值,都无法确切知道,只能凭经验来取。

    五、快速排序

      快速排序是冒泡排序的改进版,是目前已知的最快的排序方法。

      已知一组无序数据a[1]、a[2]、……a[n],需将其按升序排列。首先任取数据a[x]作为基准。比较a[x]与其它数据并排序,使a[x]排在数据的第k位,并且使a[1]~a[k-1]中的每一个数据<a[x],a[k+1]~a[n]中的每一个数据>a[x],然后采用分治的策略分别对a[1]~a[k-1]和a[k+1]~a[n]两组数据进行快速排序。

    优点:极快,数据移动少;

    缺点:不稳定。

    六、箱排序

    已知一组无序正整数数据a[1]、a[2]、……a[n],需将其按升序排列。首先定义一个数组x[m],且m>=a[1]、a[2]、……a[n],接着循环n次,每次x[a]++.

    优点:快,效率达到O(1)。

    缺点:数据范围必须为正整数并且比较小。

    插入算法的算法描述:

      一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:

      1. 从第一个元素开始,该元素可以认为已经被排序

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

      3. 如果该元素(已排序)大于新元素,将该元素移到下一位置

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

      5. 将新元素插入到该位置中

      6. 重复步骤2

    如果比较操作的代价比交换操作大的话,可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种,称为二分查找排序。

    示例代码:

    示例代码为C语言,输入参数中,需要排序的数组为array[],起始索引为first,终止索引为last。示例代码的函数采用in-place排序,调用完成后,array[]中从first到last处于升序排列。

    void insertion_sort(char array[], unsigned int first, unsigned int last)
    {
      int i,j;
      int temp;
      for (i = first+1; i<=last;i++)
      {
      temp = array;
      j=i-1;
      //与已排序的数逐一比较, 大于temp时, 该数移后
      while((j>=first) && (array[j] > temp))
      {
      array[j+1] = array[j];
      j--;
      }
      array[j+1] = temp;
      }
      }
      这个更好:
      void InsertSort(char array[],unsigned int n)
      {
      int i,j;
      int temp;
      for(i=1;i<n;i++)
      {
      temp = array;//store the original sorted array in temp
      for(j=i ; j>0 && temp < array[j-1] ; j--)//compare the new array with temp
      {
      array[j]=array[j-1];//all larger elements are moved one pot to the right
      }
      array[j]=temp;
      }
      }
      这个是c++语言版本的插入排序。为了支持list使用了std::advance()。
      #include <iterator>
      template<typename biIter>
      void insertion_sort(biIter begin, biIter end)
      {
      typedef typename std::iterator_traits<biIter>::value_type value_type;
      biIter bond = begin;
      std::advance(bond, 1);
      for(; bond!=end; std::advance(bond, 1)) {
      value_type key = *bond;
      biIter ins = bond;
      biIter pre = ins;
      std::advance(pre, -1);
      while(ins!=begin && *pre>key) {
      *ins = *pre;
      std::advance(ins, -1);
      std::advance(pre, -1);
      }
      *ins = key;
      }
    }
    展开全文
  • Java常见排序方法

    千次阅读 2019-03-10 14:41:28
    日常操作中常见的排序方法有:冒泡排序、快速排序、选择排序、插入排序、希尔排序,甚至还有基数排序、鸡尾酒排序、桶排序、鸽巢排序、归并排序等。 以下常见算法的定义 1. 插入排序:插入排序基本操作就是将一个...

    日常操作中常见的排序方法有:冒泡排序、快速排序、选择排序、插入排序、希尔排序,甚至还有基数排序、鸡尾酒排序、桶排序、鸽巢排序、归并排序等。

    以下常见算法的定义

    • 1. 插入排序:插入排序基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。插入排序的基本思想是:每步将一个待排序的纪录,按其关键码值的大小插入前面已经排序的文件中适当位置上,直到全部插入完为止。
    • 2. 选择排序:选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
    • 3. 冒泡排序:冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端。
    • 4. 快速排序:快速排序(Quicksort)是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
    • 5. 归并排序:归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。
    • 6. 希尔排序:希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

    一、冒泡排序

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

    /**  
     *  冒泡法排序   
     *  比较相邻的元素。如果第一个比第二个小,就交换他们两个。 
     *  对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最小的数。   
     *  针对所有的元素重复以上的步骤,除了最后一个。  
     *  持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。 
    
     *   
     * @param numbers  
     *            需要排序的整型数组  
     */  
    public static void bubbleSort01(int[] numbers) {   
        int temp; // 记录临时中间值   
        int size = numbers.length; // 数组大小   
        for (int i = 0; i < size - 1; i++) {   
            for (int j = i + 1; j < size; j++) {   
                if (numbers[i] < numbers[j]) { // 交换两数的位置   
                    temp = numbers[i];   
                    numbers[i] = numbers[j];   
                    numbers[j] = temp;   
                }   
            }   
        }   
    }

    注意:以上不知是什么排序,将基准位置的元素和后面的元素进行比较,如果基准位置值比后面元素小,则交换位置,交换后的元素为新的基准元素。以下才是真正的冒泡排序。

    public static void bubbleSort(int[] a) {
        int temp;
        int size = a.length;
        for(int i=1; i<size; i++) {
            for(int j=0; j<size-i; j++) {
                if(a[j] < a[j+1]) {
                    temp = a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                }
            }
            for(int aa : a)
                System.out.print(aa+",");
            System.out.println();
        }
    }
    
    

    二、快速排序

    快速排序使用分治法策略来把一个序列分为两个子序列。

    /**  
     * 快速排序 
     *    
     *  从数列中挑出一个元素,称为“基准”  
     *  重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分割之后,  
     *  该基准是它的最后位置。这个称为分割(partition)操作。  
     *  递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。  
     *  
     * @param numbers  
     * @param start  
     * @param end  
     */  
    public static void quickSort(int[] numbers, int start, int end) {   
        if (start < end) {   
            int base = numbers[start]; // 选定的基准值(第一个数值作为基准值)   
            int temp; // 记录临时中间值   
            int i = start, j = end;   
            do {   
                while ((numbers[i] < base) && (i < end))   
                    i++;   
                while ((numbers[j] > base) && (j > start))   
                    j--;   
                if (i <= j) {   
                    temp = numbers[i];   
                    numbers[i] = numbers[j];   
                    numbers[j] = temp;   
                    i++;   
                    j--;   
                }   
            } while (i <= j);   
            if (start < j)   
                quickSort(numbers, start, j);   
            if (end > i)   
                quickSort(numbers, i, end);   
        }   
    }

    如下为完全符合快速排序定义的算法:

    public static void quickSort01(int[] a, int start, int end) {
        if(start >= end)
            return;
        int i = start;
        int j = end;
        int base = a[start];
        while(i != j) {
            while(a[j] >= base && j > i)
                j--;
            while(a[i] <= base && i < j)
                i++;
            if(i < j) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
        a[start] = a[i];
        a[i] = base;
        te(a, start, i - 1);
        te(a, i + 1, end);
    }

    三、选择排序

    选择排序是一种简单直观的排序方法,每次寻找序列中的最小值,然后放在最末尾的位置。

    /**  
     * 选择排序
     * 在未排序序列中找到最小元素,存放到排序序列的起始位置  
     * 再从剩余未排序元素中继续寻找最小元素,然后放到排序序列起始位置。  
     * 以此类推,直到所有元素均排序完毕。  
     *   
     * @param numbers  
     */  
    public static void selectSort(int[] numbers) {   
        int size = numbers.length;
       int temp;   
        for (int i = 0; i < size; i++) {   
            int k = i;   
            for (int j = size - 1; j >i; j--)  {   
                if (numbers[j] < numbers[k]) {
             k = j;   
           }
            }   
            temp = numbers[i];   
            numbers[i] = numbers[k];   
            numbers[k] = temp;   
        }   
    }

    四、插入排序

    插入排序的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。其具体步骤参见代码及注释。

    /**  
     * 插入排序   
     *   
     *  从第一个元素开始,该元素可以认为已经被排序 
     *  取出下一个元素,在已经排序的元素序列中从后向前扫描  
     *  如果该元素(已排序)大于新元素,将该元素移到下一位置   
     *  重复步骤3,直到找到已排序的元素小于或者等于新元素的位置   
     *  将新元素插入到该位置中   
     *  重复步骤2    
     * @param numbers  
     */  
    public static void insertSort(int[] numbers) {   
        int size = numbers.length, temp, j;   
        for(int i=1; i<size; i++) {   
            temp = numbers[i];   
            for(j = i; j > 0 && temp < numbers[j-1]; j--)   
                numbers[j] = numbers[j-1];   
            numbers[j] = temp;   
        }   
    }

    五、归并排序

    归并排序是建立在归并操作上的一种有效的排序算法,归并是指将两个已经排序的序列合并成一个序列的操作。

    /**  
     * 归并排序   
     *   
     *  申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 
     *  设定两个指针,最初位置分别为两个已经排序序列的起始位置   
     *  比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 
     *  重复步骤3直到某一指针达到序列尾   
     *  将另一序列剩下的所有元素直接复制到合并序列尾  
     *   
     * @param numbers  
     */  
    public static void mergeSort(int[] numbers, int left, int right) {   
        int t = 1;// 每组元素个数   
        int size = right - left + 1;   
        while (t < size) {   
            int s = t;// 本次循环每组元素个数   
            t = 2 * s;   
            int i = left;   
            while (i + (t - 1) < size) {   
                merge(numbers, i, i + (s - 1), i + (t - 1));   
                i += t;   
            }   
            if (i + (s - 1) < right)   
                merge(numbers, i, i + (s - 1), right);   
        }   
    }
    /**  
     * 归并算法实现  
     *   
     * @param data  
     * @param p  
     * @param q  
     * @param r  
     */  
    private static void merge(int[] data, int p, int q, int r) {   
        int[] B = new int[data.length];   
        int s = p;   
        int t = q + 1;   
        int k = p;   
        while (s <= q && t <= r) {   
            if (data[s] <= data[t]) {   
                B[k] = data[s];   
                s++;   
            } else {   
                B[k] = data[t];   
                t++;   
            }   
            k++;   
        }   
        if (s == q + 1)   
            B[k++] = data[t++];   
        else  
            B[k++] = data[s++];   
        for (int i = p; i <= r; i++)   
            data[i] = B[i];   
    }
    
    转载
    https://www.cnblogs.com/wangmingshun/p/5635292.html
    展开全文
  • 稳定排序与不稳定排序方法

    千次阅读 2018-08-28 17:52:15
    稳定排序与不稳定排序方法  首先,排序算法的稳定性大家应该都知道,通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj,Ai原来在...

    稳定排序与不稳定排序方法

           首先,排序算法的稳定性大家应该都知道,通俗地讲就是能保证排序前2个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。在简单形式化一下,如果Ai = Aj,Ai原来在位置前,排序后Ai还是要在Aj位置前。

    其次,说一下稳定性的好处。排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。另外,如果排序算法稳定,对基于比较的排序算法而言,元素交换的次数可能会少一些(个人感觉,没有证实)。

    回到主题,现在分析一下常见的排序算法的稳定性,每个都给出简单的理由。

    (1)冒泡排序

    冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,我想你是不会再无聊地把他们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

    (2)选择排序

    选择排序是给每个位置选择当前元素最小的,比如给第一个位置选择最小的,在剩余元素里面给第二个元素选择第二小的,依次类推,直到第n - 1个元素,第n个元素不用选择了,因为只剩下它一个最大的元素了。那么,在一趟选择,如果当前元素比一个元素小,而该小的元素又出现在一个和当前元素相等的元素后面,那么交换后稳定性就被破坏了。比较拗口,举个例子,序列5 8 5 2 9,我们知道第一遍选择第1个元素5会和2交换,那么原序列中2个5的相对前后顺序就被破坏了,所以选择排序不是一个稳定的排序算法。

    (3)插入排序 
    插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。

    (4)快速排序 
    快速排序有两个方向,左边的i下标一直往右走,当a[i] <= a[center_index],其中center_index是中枢元素的数组下标,一般取为数组第0个元素。而右边的j下标一直往左走,当a[j] > a[center_index]。如果i和j都走不动了,i <= j,交换a[i]和a[j],重复上面的过程,直到i > j。 交换a[j]和a[center_index],完成一趟快速排序。在中枢元素和a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为5 3 3 4 3 8 9 10 11,现在中枢元素5和3(第5个元素,下标从1开始计)交换就会把元素3的稳定性打乱,所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和a[j] 交换的时刻。

    (5)归并排序 
    归并排序是把序列递归地分成短序列,递归出口是短序列只有1个元素(认为直接有序)或者2个序列(1次比较和交换),然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。可以发现,在1个或2个元素时,1个元素不会交换,2个元素如果大小相等也没有人故意交换,这不会破坏稳定性。那么,在短的有序序列合并的过程中,稳定是是否受到破坏?没有,合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在结果序列的前面,这样就保证了稳定性。所以,归并排序也是稳定的排序算法。

    (6)基数排序 
    基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序,最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以其是稳定的排序算法。

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

    (8)堆排序 
    我们知道堆的结构是节点i的孩子为2 * i和2 * i + 1节点,大顶堆要求父节点大于等于其2个子节点,小顶堆要求父节点小于等于其2个子节点。在一个长为n 的序列,堆排序的过程是从第n / 2开始和其子节点共3个值选择最大(大顶堆)或者最小(小顶堆),这3个元素之间的选择当然不会破坏稳定性。但当为n / 2 - 1, n / 2 - 2, ... 1这些个父节点选择元素时,就会破坏稳定性。有可能第n / 2个父节点交换把后面一个元素交换过去了,而第n / 2 - 1个父节点把后面一个相同的元素没 有交换,那么这2个相同的元素之间的稳定性就被破坏了。所以,堆排序不是稳定的排序算法。

    综上,得出结论: 选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,而冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法

     

     

     

     

    不稳定的排序算法有:快、希、选、堆。(记忆:找到工作就可以“快些选一堆”美女来玩了(并不能))

     

    展开全文
  • c语言的5种常用排序方法

    千次阅读 2020-03-09 15:39:25
    冒泡排序是最简单的排序方法:原理是:从左到右,相邻元素进行比较。每次比较一轮,就会找到序列中最大的一个或最小的一个。这个数就会从序列的最右边冒出来。(注意每一轮都是从a[0]开始比较的) 以从小到大排序为...
  • C#常用的排序方法

    千次阅读 2019-06-01 11:36:22
    快速排序由于排序效率综合来说你几种排序方法中效率较高,因此经常被采用,再加上快速排序思想----分治法也确实实用.快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略,通常称其为分治...
  • C++之五种排序方法总结

    万次阅读 多人点赞 2018-08-10 17:08:04
    模板函数sort( ) sort是一个模板函数:sort( ),括号里可以接受两个或三个参数。这里先说一下两个参数的,因为三个参数的还没研究好,哈哈。...第一个参数是所要排序的数列的首地址,而第二个参数是该数列的最后...
  • 数据结构-算法-排序-常用排序方法简介

    千次阅读 多人点赞 2018-11-02 21:01:11
    声明:此文章仅供学习排序方法的原理,不附加代码   一。常用排序方法 1. 冒泡排序(Bubble Sort) 2. 直接选择排序(Straight Selection Sort) 3. 直接插入排序(Straight Insertion Sort) 4. 希尔排序...
  • Set排序方法

    万次阅读 2019-04-22 21:04:28
    在讲解Set集合排序的几种方法之前,我们应该先清楚Set集合的几种类型以及特点,才能有效使用起来。 Set集合的特点 ​ Set不允许包含相同的元素,如果试图把两个相同元素加入同一个集合中,add方法返回false。 ​ ...
  • 【题目】python中的排序函数sorted以及列表排序方法sort()   概述 Python list内置sort()方法用来排序,也可以用python内置的全局sorted()方法来对可迭代的序列排序生成新的序列。如果要读取文件夹下面的文件,...
  • 什么是稳定的排序方法

    千次阅读 2019-10-30 21:39:40
    什么是稳定的排序方法 稳定的排序方法 设关键字Ki=Kj,且排序前的序列中Ki领先于Kj,若排序后Ki仍然领先于Kj,则称这个排序方法是稳定的 不稳定排序:快速排序、希尔排序、堆排序 稳定排序:冒泡排序,直接插入排序...
  • 稳定排序与不稳定排序方法的分类和总结

    千次阅读 多人点赞 2019-09-21 14:03:41
    排序算法的稳定性是指排序前 2 个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。简单来说就是,如果Ai = Aj,Ai原来在位置前,排序后Ai还是要在Aj位置前。 排序算法如果是稳定的,那么从一个...
  • C语言各种排序方法总结。

    千次阅读 2019-01-19 09:27:07
    今天接到中软国际的dsp开发的技术面试,问了我字符串排序如何进行排序,把有关排序的问题总结一下。 目前能够在网上搜寻到的排序有: 第一(NUM_ONE): 冒泡排序(BubbleSort) 第二(NUM_TWO): 快速排序...
  • python:列表排序方法

    千次阅读 2018-12-16 22:04:07
    使用Python内置sort()方法用来排序,也可以用python内置的全局sorted()方法来对可迭代的序列排序生成新的序列。 sorted()方法: 简单的升序排序是非常容易的。只需要调用sorted()方法。它返回一个新的list,新的...
  • 常见的几种排序方法

    千次阅读 2019-06-01 09:34:54
    【常见的几种排序方法】 1.背景介绍 在计算机科学与数学中,一个排序算法(英语:Sorting algorithm)是一种能将一串资料依照特定排序方式进行排列的一种算法。 最常用到的排序方式是数值顺序以及字典顺序。有效的...
  • 排序趟数 与序列初态 无关 的算法是:直接插入排序、折半插入排序、希尔排序、简单选择排序、归并排序、基数排序 排序趟数与序列初态 有关 的算法是:冒泡排序、快速排序 关于排序趟数 插入排序、选择排序 趟数都是...
  • 冒泡排序,选择排序和插入排序算得上是最基本的三种排序方式了,当年我的c语言老师和我们说,冒泡排序和选择排序能会一个就行了,结果c语言考试(机考)有一个沙雕题的评测库只能用冒泡才能过,于是我一个经常用选择...
  • 图解常见排序方法的时间复杂度

    千次阅读 2018-10-08 22:09:12
    常见排序方法及其复杂度 几种复杂的表示方式: O(1): 耗时/耗空间与输入数据大小无关 O(n): 就代表数据量增大几倍,耗时也增大几倍。比如常见的遍历算法。 O(n2),就代表数据量增大n倍时,耗时增大n的平方倍,...
  • 快速排序(quick sorting)是对气泡排序的一种改进,是关键字次数少,速度较快的一种排序方法。 2 基本思想 简单概括就是:给基准数据找到其正确的索引位置; 具体原理如下: 1)如下图所示,假设目前的基准数据是第...
  • 三种基本排序方法(C语言实现)

    万次阅读 多人点赞 2018-05-24 00:19:08
    三种基本排序(以升序为例) 1.冒泡排序 思想:每次相邻两个数比较,若升序,则将大的数放到后面,一次循环过后,就会将最大的数放在最后. 如图9 3 2 5 8 4 7 6是输入的待排序的数列,经过第一次排序,将最大的9放在...
  • Python中列表的排序方法

    万次阅读 多人点赞 2019-01-26 16:25:11
    一、sort()排序方法 # 这个方法会改变a自身 a = [7,5,9,3] # True为逆序,False为正序 a.sort(reverse = False) print(a) a.sort(reverse = True) print(a) [3, 5, 7, 9] [9, 7, 5, 3] 二、sorted()排序方法 # 用...
  • 两种排序方法(用c++实现)

    千次阅读 2020-06-09 15:45:19
    考拉最近学习到有两种字符串的排序方法: 1.根据字符串的字典序排序。例如: "car" < "carriage" < "cats" < "doggies < "koala" 2.根据字符串的长度排序。例如: "car" < "cats" < "koala" < ...
  • Java排序方法sort的使用

    千次阅读 2019-07-26 15:44:59
    为方便查阅sort相关使用,自己做的一个整理,可能有点乱并且不全,后续有机会再补充。 对数组的排序: //对数组排序 public void arraySort...//使用java.util.Arrays对象的sort方法 for(int i=0;i<arr.leng...
  • 常见的排序方法有哪些?

    千次阅读 2018-06-29 16:11:20
    大家好,我是IT修真院郑州分院第八期的学员,今天给大家分享一下,题目常见的排序方法有哪些。 一、背景介绍 排序算法(英语:Sorting algorithm)是一种能将一串资料依照特定排序方式进行排列的一种算法。最常...
  • java常用的8种排序方法

    万次阅读 多人点赞 2017-09-13 14:36:53
    1.直接插入排序 经常碰到这样一类排序问题:把新的数据插入到已经排好的数据列中。 将第一个数和第二个数排序,然后构成一个有序序列将第三个数插入进去,构成一个新的有序序列。 对第四个数、第五个数……直到...
  • c语言几种排序方法

    千次阅读 2018-07-17 17:54:39
    2.几种排序方法。冒泡排序:循环进行比较,依次将最小的数冒出来。 void Bubble_sort(int a[],int len) { int i,j; int flag=FALSE; //FALSE代表序列依旧为乱序 for(i=1;i;i++) { flag=TRUE; for(j=0;j...
  • python 列表排序方法sort、sorted技巧篇

    万次阅读 2018-03-29 13:34:37
    Python list内置sort()方法用来排序,也可以用python内置的全局sorted()方法来对可迭代的序列排序生成新的序列。1)排序基础简单的升序排序是非常容易的。只需要调用sorted()方法。它返回一个新的list,新的list的...
  • 列表中元素的几种排序方法

    千次阅读 2019-06-30 11:54:27
    一般的排序方法sort(),属于python的内置方法 names = ['alice','Bob','coco','Harry'] print(names.sort()) 将列表打乱 li = list(range(10)) import random random.shuffle(li) print(li) ...
  • 要求首先随机产生10000个数据存入磁盘文件,然后读入数据文件,分别采用不同的排序方法进行排序并将结果存入文件中。一、算法思想描述(用一个长度为10的序列进行模拟)1.希尔排序希尔排序是对直接插入排序的改进,...
  • springboot-data-jpa常用排序方法汇总

    千次阅读 2019-09-27 15:38:52
    springboot-jpa默认方法支持排序,当然复杂的场景需要自己重写默认的方法,下面介绍三种排序方法 首先需要定义一个依赖的对象 @Data public class Person{ private Integer id; private String name; ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,306,012
精华内容 522,404
关键字:

排序方法