精华内容
下载资源
问答
  • 内排序要求数据一定以顺序方式存储
    千次阅读
    2019-09-22 12:09:31

    判断题

    1.希尔排序是稳定的算法。

         T      F

    稳定的算法:保证排序前两个相等的数其在序列的前后位置顺序和排序后它们两个的前后位置顺序相同。

    希尔排序会多次进行插入排序,一次插入排序是稳定的,但是因为希尔排序每次插入排序选择的步长不一样,导致希尔排序不稳定。

    2.仅基于比较的算法能得到的最好的“最坏时间复杂度”是O(NlogN)。

         T      F

    仅基于比较的算法能得到的最好的“最好时间复杂度”是O(N),仅基于比较的算法能得到的最好的“最坏时间复杂度”是O(NlogN)。

    3.(neuDS)直接插入排序算法在最好情况下的时间复杂度为O(n)。

         T      F

    4.内排序要求数据一定要以顺序方式存储。

         T      F

    内排序是完全在内存中存放待排序元素的排序,存储形式不一定是顺序的。

    5.排序算法中的比较次数与初始元素序列的排列无关。

         T      F

    6.排序的稳定性是指排序算法中的比较次数保持不变,且算法能够终止。

         T      F

    7.对N个记录进行堆排序,需要的额外空间为O(N)。

         T      F

    不需要额外的空间。

    8.堆排序是稳定的排序算法。( )

         T      F

    因为堆没有规定相同的元素应该放在左子树还是右子树,所以堆排序是不稳定的。

    9.在堆排序中,若要进行升序排序,则需要建立大根堆。( )

         T      F

    10.对N个记录进行快速排序,在最坏的情况下,其时间复杂度是O(NlogN)。

         T      F

    11.在初始数据表已经有序时,快速排序算法的时间复杂度为O(nlogn )

         T      F

    快速排序的时间复杂度和是否有序无关。

    12.当待排序记录已经从小到大排序或者已经从大到小排序时,快速排序的执行时间最省。

         T      F

    13.快速排序的速度在所有排序方法中为最快,而且所需附加空间也最少。

         T      F

    选择题

    1.下列排序算法中,哪种算法可能出现:在最后一趟开始之前,所有的元素都不在其最终的位置上?(设待排元素个数N>2)

        A.冒泡排序
        B.插入排序
        C.堆排序
        D.快速排序

    2.对初始数据序列{ 8, 3, 9, 11, 2, 1, 4, 7, 5, 10, 6 }进行希尔排序。若第一趟排序结果为( 1, 3, 7, 5, 2, 6, 4, 9, 11, 10, 8 ),第二趟排序结果为( 1, 2, 6, 4, 3, 7, 5, 8, 11, 10, 9 ),则两趟排序采用的增量(间隔)依次是:

        A.3, 1
        B.3, 2
        C.5, 2
        D.5, 3
    index012345678910
    first8391121475106
    second1375264911108

    红色部分可以看出,第一次的增量是5。

    红色部分可以看出,第二次的增量是3。

    3.对关键字序列(56,23,78,92,88,67,19,34),进行增量为3的一趟希尔排序的结果为( )。

        A.(19,23,56,34,78,67,88,92)
        B.(23,56,78,66,88,92,19,34)
        C.(19,23,34,56,67,78,88,92)
        D.(19,23,67,56,34,78,92,88)

    4.有组记录的排序码为{ 46,79,56,38,40,84 },则利用堆排序的方法建立的初始堆为:

        A.79,46,56,38,40,80
        B.84,79,56,46,40,38
        C.84,56,79,40,46,38
        D.84,79,56,38,40,46

    5.对N个记录进行堆排序,最坏的情况下时间复杂度是:

        A.O(logN)
        B.O(N)
        C.O(NlogN)
        D.O(N 2)

    最坏的情况下,堆元素下滤都从顶部下滤到底部,为logN,一共N个元素,所以总的时间复杂度是O(NlogN)。

    6.对N个记录进行堆排序,需要的额外空间为:

        A.O(1)
        B.O(logN)
        C.O(N)
        D.O(NlogN)

    7.在含有n个关键字的小根堆中,关键字最大的记录有可能存储在()位置上。

        A.n/2 +2
        B.1
        C.n/2 -1
        D.n/2

    堆的性质。

    8.有一组数据(15,9,7,8,20,-1,7,4),用堆排序的筛选方法建立的初始堆为()。

        A.-1,4,8,9,20,7,15,7
        B.-1,7,15,7,4,8,20,9
        C.-1,4,7,8,20,15,7,9
        D.A,B,C均不对。

    9.下列关键字序列中,构成大根堆的是( )。

        A.5,8,1,3,9,6,2,7
        B.9,8,1,7,5,6,2,3
        C.9,8,6,3,5,1,2,7
        D.9,8,6,7,5,1,2,3

    10.采用递归方式对顺序表进行快速排序,下列关于递归次数的叙述中,正确的是:

        A.每次划分后,先处理较长的分区可以减少递归次数
        B.每次划分后,先处理较短的分区可以减少递归次数
        C.递归次数与每次划分后得到的分区处理顺序无关
        D.递归次数与初始数据的排列次序无关

    11.对N个记录进行快速排序,在最坏的情况下,其时间复杂度是:

        A.O(N)
        B.O(NlogN)
        C.O(N 2)
        D.O(N 2logN)

    12.在快速排序的一趟划分过程中,当遇到与基准数相等的元素时,如果左右指针都会停止移动,那么当所有元素都相等时,算法的时间复杂度是多少?

        A.O(logN)
        B.O(N)
        C.O(NlogN)
        D.O(N 2)

    指针停止就会不断交换左右指针的元素,这样虽然多余的交换次数变多,但让子序列的元素相对平均,所以一共有logN次划分,每次时间复杂度是O(N)。

    13.在快速排序的一趟划分过程中,当遇到与基准数相等的元素时,如果左右指针都不停止移动,那么当所有元素都相等时,算法的时间复杂度是多少?

        A.O(logN)
        B.O(N)
        C.O(NlogN)
        D.O(N 2)

    指针不停止,导致所有元素都被放到一个划分中去,一共N个元素,所以一共有N次划分,每次时间复杂度是O(N)。

    14.执行一趟快速排序能够得到的序列是( )。

        A.[41,12,34,45,27] 55 [72,63]
        B.[45,34,12,41] 55 [72,63,27]
        C.[63,12,34,45,27] 55 [41,72]
        D.[12,27,45,41] 55 [34,63,72]

    15.有一组数据(15,9,7,8,20,-1,7,4) 用快速排序的划分方法进行一趟划分后数据的排序为 ( )(按递增序)。

        A.9,7,8,4,-1,7,15,20
        B.20,15,8,9,7,-1,4,7
        C.9,4,7,8,7,-1,15,20
        D.4,9,7,8,7,-1,15,20

    16.有组记录的排序码为{46,79,56,38,40,84 },采用快速排序(按教材算法操作),以位于最左位置的对象为主元得到的第一次划分结果为:

        A.{38,46,79,56,40,84}
        B.{38,79,56,46,40,84}
        C.{40,38,46,79,84,56}
        D.{40,38,46,56,79,84}

    17.用快速排序方法对线性表(25,84,21,47,15,27,68,35,20)进行排序时,以位于最左位置的对象为主元,得到的第一次划分结果为(按教材算法操作):

        A.20,15,21,25,47,27,68,35,84
        B.15,20,21,25,35,27,47,68,84
        C.15,20,21,25,27,35,47,68,84
        D.20,15,21,25,84,27,68,35,47

    填空题

    1.本题要求用冒泡排序将一组整数按增序排序。冒泡排序每次从头到尾扫描待排序列,检查相邻两数的顺序,如果顺序不对就交换。请补全下列冒泡排序的代码。

    typedef struct node *nodeptr;
    struct node{
        int value;
        nodeptr next;
        /* 一些其他的项,在此忽略 */
    };

    nodeptr BubbleSort (nodeptr h)
    {/* h 是带空头结点的链表的头指针 */
        nodeptr p, q;
        int flag_swap;

        if (!h->next) return h;
        do{
            flag_swap = 0;
            p = h;
            while (p->next->next){
                if (     (3分) ){
                    flag_swap++;
                    q = p->next;
                        (3分);
                        (3分);
                        (3分);
                }
                else p = p->next;
            }
        } while (flag_swap > 0);
        return h;
    }

    2.下列代码的功能是利用堆排序将N个元素按非递减顺序排序。

    #define leftchild(i) ( 2*(i)+1 )

    void PercDown( ElementType A[], int i, int N )
    {   int child;
        ElementType Tmp;

        for ( Tmp = A[i]; leftchild(i) < N; i = child ) {
            child = leftchild(i);
            if (    (3分))
                child ++;
            if (    (3分)) A[i] = A[child];
            else break;
        }
            (3分);
    }
    void Heapsort( ElementType A[ ], int N )
    {   int i;
        for ( i = N / 2; i >= 0; i -- ) /* BuildHeap */
            PercDown( A, i, N );
        for ( i = N-1; i > 0; i -- ) {
            Swap( &A[ 0 ], &A[ i ] );
                (3分);
        }
    }

    3.下列代码的功能是将一列元素{ r[1] … r[n] }按其键值 key 的非递减顺序排序。普通选择排序是每次仅将一个待排序列的最小元放到正确的位置上,而这个另类的选择排序是每次从待排序列中同时找到最小元和最大元,把它们放到最终的正确位置上。

    void sort( list r[], int n )
    {
        int i, j, mini, maxi;

        for (i=1; i<n-i+1; i++) {
            mini = maxi = i;
            for( j=i+1;     (3分); ++j ){
                if(      (3分) ) mini = j;
                else if(r[j]->key > r[maxi]->key) maxi = j;
            }
            if(     (3分) ) swap(&r[mini], &r[i]);
            if( maxi != n-i+1 ){
                if(     (3分) ) swap(&r[mini], &r[n-i+1]);
                else swap(&r[maxi], &r[n-i+1]);
            }
        }
    }

    4.本函数的功能是从有N个元素的线性表A中查找第K小的元素。函数的初始调用为Qselect(A, K, 0, N-1)。请完成下列填空。

    ElementType Qselect( ElementType A[], int K, int Left, int Right )
    {
        ElementType Pivot = A[Left];
        int L = Left, R = Right+1;

        while (1) {
            while ( A[++L] < Pivot ) ;
                (3分);
            if ( L < R ) Swap( &A[L], &A[R] );
            else break;
        }
        Swap( &A[Left], &A[R] );
        if ( K < (L-Left) )
            return Qselect(A, K, Left, R-1);
        else if ( K > (L-Left) )
                (3分);
        else
            return Pivot;
    }

    5.本题要求实现快速排序操作,待排序列的长度1<=n<=1000。 使排序后的数据从小到大排列。

    类型定义:

    typedef int KeyType;
    typedef struct {
        KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/
        int Length;
    }SqList;

    程序:

    #include<stdio.h>
    #include<stdlib.h>
    typedef int KeyType;
    typedef struct {
        KeyType *elem; /*elem[0]一般作哨兵或缓冲区*/
        int Length;
    }SqList;
    void CreatSqList(SqList *L);/*待排序列建立,由裁判实现,细节不表*/
    int Partition ( SqList L,int low, int high );
    void Qsort ( SqList L,int low, int high );
    int main()
    {
        SqList L;
        int i;
        CreatSqList(&L);
        Qsort(L,1,L.Length);
        for(i=1;i<=L.Length;i++)
        {
            printf("%d ",L.elem[i]);
        }
        return 0;
    }
    int Partition ( SqList L,int low, int high )
    { /*一趟划分*/
        KeyType pivotkey;
        L.elem[0] = L.elem[low];
        pivotkey = L.elem[low];
        while(low<high)
        {
            while ( low < high && L.elem[high] >= pivotkey )
                --high;
            L.elem[low] = L.elem[high];
            while ( low < high && L.elem[low] <= pivotkey )
                ++low;
            L.elem[high] = L.elem[low];
        }
        L.elem[low]=L.elem[0];
        return low;
    }
    void Qsort ( SqList L,int low, int high )
    {
        int pivotloc;
        if (     (2分) )
        {
            pivotloc = Partition(L, low, high ) ;
            Qsort (     (2分)) ;
                (2分);
        }
    }

    输入样例:

    第一行整数表示参与排序的关键字个数。第二行是关键字值 例如:

    10
    5 2 4 1 8 9 10 12 3 6

    输出样例:

    输出由小到大的有序序列,每一个关键字之间由空格隔开,最后一个关键字后有一个空格。

    1 2 3 4 5 6 8 9 10 12

    转载于:https://www.cnblogs.com/nonlinearthink/p/11082433.html

    更多相关内容
  • 输入n个整数,分别用希尔排序、快速排序、堆排序和归并排序实现由小到大排序并输出排序结果。要求n=10,15,20进行三组排序实验。 实验目的:掌握希尔排序、快速排序、堆排序、归并排序算法。 (zip中含代码及运行...
  • 直接插入排序顺序存储、链式存储),折半插入排序顺序存储),希尔排序顺序存储) 插入排序 直接插入排序 将元素插入L[i]插入到已有序的子序列L[i-1]中。其基本思想是每次将一个待排序的记录按其关键字大小...

    直接插入排序(顺序存储、链式存储),折半插入排序(顺序存储),希尔排序(顺序存储)

    插入排序

    直接插入排序
      ​将元素插入L[i]插入到已有序的子序列L[i-1]中。其基本思想是每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中,直到全部记录插入完成。基本步骤如下:
    1)查找出L[i]在L[1]~L[i-1]中要插入的位置K;
    2)将L[i]的值复制到L[0];
    3)将L[K]~L[i-1]中的所有元素依次后移一个位置;
    4)将L[0]的值复制到L[K];
    空间复杂度:O(1)
    最好时间复杂度(全部有序):O(n)
    最坏时间复杂度(全部逆序):O(n^2)
    平均时间复杂度:O(n2)
    算法稳定性:稳定

    折半插入排序
      ​顺序存储的线性表可以用折半查找来实现。用折半查找来确定待插入的位置后,就可以统一的向后移动元素。基本步骤如下:
    1)当 low>high 时折半查找停止,应将 [low, i-1] 内的元素全部右移,并将 A[0] 复制到 low 所指位置;
    2)当 A[mid]==A[0] 时,为了保证算法的“稳定性”,应继续在 mid 所指位置右边寻找插⼊位置。
    空间复杂度:O(1)
    时间复杂度:移动元素的次数变少了,但是关键字对比的次数依然是O(n2) 数量级,整体来看时间复杂度依然是O(n^2)
    算法稳定性:不稳定

    顺序存储结构

    /*
    Project:InsertSort(直接插入排序)
    Data:2020/11/18
    Author:F&S&L
    InitList(SqList &L) 参数:顺序表L
    CreateList(SqList &L,int n) 参数:顺序表L,顺序表中元素个数n
    InitList(SqList &L) 参数:顺序表L
    Create(SqList &L) 参数:顺序表L
    InsertSort(SqList &L) 参数:顺序表L
    HalfInsertSort(SqList &L) 参数:顺序表L
    */ 
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<algorithm>
    #include<iostream>
    #define MaxSize 100
    #define ElemType int
    #define Status int
    using namespace std;
    
    //顺序表数据结构
    typedef struct
    {
    	ElemType data[MaxSize];
    	int length;
    } SqList;
    //初始化顺序表函数,构造一个空的顺序表
    Status InitList(SqList &L)
    {
     	memset(L.data,0,sizeof(L));
     	L.length=0;
     	return 0;
    } 
    //打印输出顺序表
    void PrintList(SqList L)
    {
    	for(int i=1;i<L.length+1;i++)
    	{
    		printf("%d ",L.data[i]);
    	}
    	printf("\n");
    } 
    //初始化顺序表函数
    bool CreateList(SqList &L,int n)
    {
    	if(n<0||n>MaxSize)false;
    	for(int i=1;i<n+1;i++)
    	{
    		scanf("%d",&L.data[i]);
    		L.length++;
    	}
    	return true;
    } 
    //创建顺序表函数
    void Create(SqList &L)
    {
    	int n;
    	bool flag;
    	printf("请输入要创建的顺序表长度(>1):");
    	scanf("%d",&n);
    	printf("请输入%d个数(空格隔开):",n);
    	flag=CreateList(L,n);
    	if(flag)
    	{
    		printf("创建成功后的元素:");
    		PrintList(L);
    	}
    	else printf("输入长度非法!!!\n");
     } 
    //直接插入排序 ,升序排序 
    void InsertSort(SqList &L)
    {
    	int i,j;
    	for (i=2;i<L.length+1;i++)
    	{
    		if(L.data[i]<L.data[i-1])
    		{
    			L.data[0]=L.data[i];
    			L.data[i]=L.data[i-1];
    			for(j=i-2;L.data[0]<L.data[j];j--)
    			{
    				L.data[j+1]=L.data[j];
    			}
    			L.data[j+1]=L.data[0];
    		}
    	}
    	printf("直接插入排序后的元素:") ;
    	PrintList(L);
    } 
    //折半插入排序
    void HalfInsertSort(SqList &L)
    {
    	int i,j,low,high,mid;
    	for(i=2;i<L.length+1;i++)
    	{
    		L.data[0]=L.data[i];
    		low=1;
    		high=i-1;
    		while(low<=high)
    		{
    			mid=(low+high)/2;
    			if(L.data[mid]>L.data[0])high=mid-1;
    			else low=mid+1;
    		}
    		for(j=i-1;j>=high+1;j--)
    		{
    			L.data[j+1]=L.data[j];
    		 } 
    		L.data[high+1]=L.data[0];
    	}
    	printf("折半插入排序后的元素:");
    	PrintList(L); 
    }
    //主函数 
    int main()
    {
     	SqList L;
     	InitList(L);
     	Create(L);
     	InsertSort(L);
     	HalfInsertSort(L);
     }
    

    在这里插入图片描述
    链式存储结构

     /*
    Project:LinkInsertSort(直接插入排序)
    Data:2020/11/18
    Author:F&S&L
    InitList(LinkList &L) 参数:链表L
    ListLength(LinkList L) 参数:链表L
    InsertList(LinkList &L,ElemType e) 参数:链表L,待插入元素e
    PrintList(LinkList L) 参数:链表L
    Sort(LinkList &L) 参数:链表L
    */ 
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    #define Status int
    #define ElemType int
    
    //单链表数据结构 
    typedef struct LNode
    {
    	ElemType data;
    	struct LNode *next;
    }LNode,*LinkList;
    //初始化一个带头结点的空链表 
    Status InitList(LinkList &L) 
    {
    	L=new LNode;
    	L->next=NULL;
    	return 1;
    }
    //获取单链表长度,头结点无数据,不算
    int ListLength(LinkList L)
    {
    	LinkList p=L;
    	int sum=0;
    	while(p)
    	{
    		sum++;
    		p=p->next;
    	}
    	return sum-1;
    }
    // 按升序插入函数 
    bool InsertList(LinkList &L,ElemType e)
    {
    	LNode* s;
    	LinkList r=L,p=L->next;
    	s=new LNode;
    	s->data=e;
    	while(p)              //当结点p不为空 
    	{
    		if(p->data<e)
    		{
    			r=r->next;
    			p=p->next;
    		}
    		else
    		{
    			s->next=p;
    			r->next=s;
    			break; 
    		}
    	}
    	s->next=p;
    	r->next=s;
    	return true;
    }
    //打印输出函数 
    void PrintList(LinkList L)
    {
    	LinkList p=L->next;
    	if(ListLength(L))
    	{
    		while(p)
    		{
    			printf("%d ",p->data);
    			p=p->next;
    		}
    		printf("\n");
    	}
    	else
    	{
    		printf("当前单链表已空!!!\n");
    	}
     }
    //排序实现函数 ,调用InsertList 
    void Sort(LinkList &L)
    {
    	int flag;
    	ElemType e;
    	printf("请输入要插入的元素:");
    	scanf("%d",&e);
    	flag=InsertList(L,e);
    	if(flag)
    	{
    		printf("排序后的元素:");
    		PrintList(L);
    	 } 
    }
    //菜单 
    void menu()
    {
    	printf("***************1.插入           2.退出***************\n");
    }
    //主函数 
    int main()
    {
    	LinkList L;
    	InitList(L);
    	int choice;
    	while(1)
    	{
    		menu();
    		printf("请输入菜单号:");
    		scanf("%d",&choice);
    		if(choice==2)
    			break;
    		switch(choice)
    		{
    			case 1:Sort(L);break;
    			default:printf("输入错误!!!\n");
    		}
    	}
    	return 0;
    }
    

    在这里插入图片描述
    希尔排序
      ​先将待排序表分割成若干形如 L[i, i + d, i + 2d,…, i + kd] 的“特殊”子表,对各个子表分别进行直接插⼊排序。缩小增量d,重复上述过程,直到d=1为止。仅适用于顺序表,不适用于链表。
    空间复杂度:O(1)
    时间复杂度:和增量序列 d1, d2, d3… 的选择有关,目前无法用数学手段证明确切的时间复杂度 最坏时间复杂度为 O(n^2),当n在某个范围内时,可达O(n1.3)
    稳定性:不稳定

    /*
    Project:ShellSort(希尔排序)
    Data:2020/11/18
    Author:F&S&L
    InitList(SqList &L) 参数:顺序表L
    CreateList(SqList &L,int n) 参数:顺序表L,顺序表中元素个数n
    PrintList(SqList L) 参数:顺序表L
    Create(SqList &L) 参数:顺序表L
    ShellSort(SqList &L) 参数:顺序表L
    */ 
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<algorithm>
    #include<iostream>
    #define MaxSize 100
    #define ElemType int
    #define Status int
    using namespace std;
    
    //顺序表数据结构
    typedef struct
    {
    	ElemType data[MaxSize];
    	int length;
    }SqList;
    //初始化顺序表函数,构造一个空的顺序表
    Status InitList(SqList &L)
    {
    	memset(L.data,0,sizeof(L));
    	L.length=0;
    	return 1;
    }
    //初始化顺序表函数
    bool CreateList(SqList &L,int n)
    {
    	if(n<0||n>MaxSize)false;
    	printf("请依次输入%d个元素(空格隔开):",n);
    	for(int i=1;i<=n;i++)
    	{
    		scanf("%d",&L.data[i]);
    		L.length++;
    	}
    	return true;
    }
    //打印输出函数  
    void PrintList(SqList L)
    {
    	for(int i=1;i<=L.length;i++)
    	{
    		printf("%d ",L.data[i]);
    	}
    	printf("\n"); 
    }
    //创建顺序表实现函数,调用 CreateList
    void Create(SqList &L)
    {
    	int n;
    	bool flag;
    	printf("请输入要创建的顺序表长度:");
    	scanf("%d",&n);
    	flag=CreateList(L,n);
    	if(flag)
    	{
    		printf("顺序表为:");
    		PrintList(L);
    	}
    }
    //希尔排序函数 
    void ShellSort(SqList &L)
    {
    	int d,i,j;
    	for(d=L.length/2;d>=1;d=d/2)
    	{
    		for(i=d+1;i<=L.length;i++)
    		{
    			if(L.data[i]<L.data[i-d])
    			{
    				L.data[0]=L.data[i];
    				for(j=i-d;j>0&&L.data[j]>L.data[0];j-=d)L.data[j+d]=L.data[j];
    				L.data[j+d]=L.data[0];
    			}
    		}
    	}
    	printf("希尔排序后的顺序表:");
    	PrintList(L);	
    }
    //主函数 
    int main()
    {
    	SqList L;
    	InitList(L);
    	Create(L);
    	ShellSort(L);
    }
    

    在这里插入图片描述

    展开全文
  • 数据结构二叉排序树的实现用顺序和二叉链表作存储结构课程设计报告.doc
  • 简单选择排序顺序存储、链式存储)、堆排序顺序存储)   选择排序分为简单选择排序和堆排序。其基本思想是:每一趟(如第i趟)在后面n-i+1(i=1,2,…,n-1)个待排序元素中选关键字最小的元素,作为有序子...

    简单选择排序(顺序存储、链式存储)、堆排序(顺序存储)

      选择排序分为简单选择排序和堆排序。其基本思想是:每一趟(如第i趟)在后面n-i+1(i=1,2,…,n-1)个待排序元素中选关键字最小的元素,作为有序子序列的第i个元素,直到第n-1趟做完,待排序元素只剩下1个,就不用再选了。

    简单选择排序

      算法思想:假设排序表为L[1…n],第i趟排序即从L[i…n]中选取关键字最小的元素与L(i)交换,每一趟排序可以确定一个元素的最终位置,这样经过n-1趟排序就可以使得整个排序表有序。
    顺序存储结构(数组)

    /*
    Title:简单选择排序(数组结构实现)
    Author:F&S&L 
    Time:2020.11.30 
    */
    #include<stdio.h>
    #include<stdlib.h>
    #define MaxSize 100
    
    int A[MaxSize];        //初始化数组 
    
    int CreateA()         //创建待排序数组A[] 
    {
    	int e,i=0;
    	printf("请输入你需要排序的元素(空格隔开,以999结束):");
    	while(1)
    	{
    		scanf("%d",&e);
    		if(e!=999)    //当从键盘输入的元素不为999时,就存储到数组A[]中;反之,则结束输入 
    		{
    			i++;      //i记录的是待排序数组中元素的个数 
    			A[i-1]=e;
    		} 
    		else break;
    	}
    	return i-1;	    //返回的i-1表示的是待排序数组中最后一个元素的下标 
    } 
    
    void SelectSort(int rear)  //简单选择排序函数,传入的参数rear表示的是最后一个元素的小标 
    {
    	int front=0,p,temp;   //front是进行比较的第一个元素的位置,p是用来记录当前比较过程中最小元素的位置,temp是交换元素的盒子 
    	while(front<rear)  //结束循环的条件 
    	{
    		p=front;       //假设当前最小元素的front 
    		for(int i=front+1;i<=rear;i++)   //如果i位置的元素小于p位置元素的值,则将i赋给p 
    		{
    			if(A[i]<A[p])
    			{
    				p=i;
    			}
    		}
    		temp=A[front];    //一趟之后,就进行元素交换,把最小元素赋给front位置,同时front+1,再进行下一趟 
    		A[front]=A[p];
    		A[p]=temp;
    		front++;
    	}
    }
    
    void PrintfA(int rear)   //打印数组A[] 
    {
    	for(int i=0;i<=rear;i++)
    	{
    		printf("%d ",A[i]);	
    	}
    	printf("\n");	
    } 
    
    int main()
    {
    	int n;
    	n=CreateA();
    	printf("待排序的序列为:");
    	PrintfA(n); 
    	SelectSort(n);
    	printf("排序后的序列为:");
    	PrintfA(n); 
    }
    
    

    在这里插入图片描述
    链式存储结构(单链表)

    /*
    Title:简单选择排序(单链表结构实现)
    Author:F&S&L 
    Time:2020.11.30 
    */
    #include<stdio.h>
    #include<stdlib.h>
    #define ElemType int
    
    typedef struct Lnode  //创建节点的数据结构 
    {
    	ElemType data;
    	struct Lnode *next;
    }LNode,*LinkList;
    
    LinkList CreateList()  //尾插法创建单链表 
    {
    	ElemType e=0;
    	LinkList L;
    	L=(LinkList)malloc(sizeof(Lnode));
    	LNode *s,*r=L;          //节点s用来存储待插入元素,指针r用来指向当前链表的尾部 
    	printf("请输入待排序元素(空格隔开,以999结束):");
    	while(e!=999)
    	{
    		scanf("%d",&e);
    		if(e!=999)
    		{
    			s=(LNode*)malloc(sizeof(Lnode));
    			s->data=e;
    			r->next=s;
    			r=s;
    		}
    		else
    		{
    			r->next=NULL;
    			break;
    		}
    	}
    	return L;
    }
    
    LinkList SelectSort(LinkList L)
    {
    	LNode *front=L->next;   //front指针指向待排序序列的第一个元素 
    	LNode *p;       //指针p用来指向来比较的元素 
    	LNode *min;     //指针min用来指向当前最小元素的位置 
    	int temp;		//temp作为交换元素的空间 
    	while(front->next!=NULL)   //当front没有指向最后一个元素时 
    	{
    		min=front;
    		p=front->next;
    		while(p->next!=NULL)
    		{
    			if(p->data<min->data)
    			{
    				min=p;
    				p=p->next;
    			}
    			else 
    			{
    				p=p->next;
    			}
    		}
    		if(p->data<min->data)min=p;   //当front指向最后一个元素时,比较最后一个元素和当前min的大小 
    		temp=front->data;        //将一趟下来min指向的值和front指向的值交换 
    		front->data=min->data;
    		min->data=temp;
    		front=front->next;     //再将front指针后移一个位置 
    	}
    	return L;
    } 
    
    void PrintfList(LinkList L)
    {
    	LNode *p=L->next;
    	while(p->next!=NULL)
    	{
    		printf("%d ",p->data);
    		p=p->next;
    	}
    	printf("%d",p->data);
    	printf("\n");
    }
    
    int main()
    {
    	LinkList L;
    	L=CreateList();
    	printf("待排序元素序列为:");
    	PrintfList(L);
    	SelectSort(L);
    	printf("排序后的元素序列为:");
    	PrintfList(SelectSort(L)); 
    }
    
    

    在这里插入图片描述
    空间效率:O(1)
    时间效率:O(n^2)
    稳定性:不稳定

    堆排序

      算法思想:首先将存放在L[1…n]中的n个元素建成初始堆,由于堆(大根堆)本身的特点,堆顶元素就是最大值。输出堆顶元素之后,通常将堆底元素送到堆顶,此时根节点已经不满足大根堆性质,堆被破坏,将堆顶元素向下调整使其继续保持大根堆的性质,再输出堆顶元素。如此重复,直到堆中只有一个元素为止。
    数组实现,基于树的顺序存储特点,i节点的左孩子是2i,右孩子是2i+1

    /*
    Title:堆排序(数组实现,基于树的顺序存储特点,i节点的左孩子是2i,右孩子是2i+1)
    Author:F&S&L 
    Time:2020.12.1 
    */
    #include<stdio.h>
    #include<stdlib.h>
    #define MaxSize 100
    
    int A[MaxSize];
    
    //用户输入待排序元素序列
    int CreateA()
    {
        int e,len=0;
        printf("请输入待排序元素序列(空格隔开,以999结束):");
        while(1)
        {
            scanf("%d",&e);
            if(e!=999)
            {
                len++;
                A[len]=e;
            }
            else
            {
                break;
            }
            
        }
        return len;   //返回待排序元素序列的长度,即元素个数
    }
    
    //建立大根堆
    void BuildMaxHeap(int A[],int len)   //预留0号位置来作为交换元素的空间
    {
        int i=len/2;
        while(i>0)
        {
            if(2*i+1<=len)     //当i号位置的右孩子存在时
            {
                if(A[2*i]>A[i]&&A[2*i+1]>A[i])  //如果左孩子和右孩子同时大于父亲节点
                {
                    if(A[2*i]-A[2*i+1]>=0)    //得比较左右孩子的值,较大的那个和父亲节点交换元素
                    {
                        A[0]=A[2*i];
                        A[2*i]=A[i];
                        A[i]=A[0];
                    }
                    else
                    {
                        A[0]=A[2*i+1];
                        A[2*i+1]=A[i];
                        A[i]=A[0];
                    }                
                }
                if(A[2*i]>A[i])   //右孩子小于父亲节点,左孩子大于父亲节点
                {
                    A[0]=A[2*i];
                    A[2*i]=A[i];
                    A[i]=A[0];
                }
                if(A[2*i+1]>A[i])   //左孩子小于父亲节点,右孩子大于父亲节点
                {
                    A[0]=A[2*i+1];
                    A[2*i+1]=A[i];
                    A[i]=A[0];
                }
            }
            i--;     //交换元素后,使i的值减1
        }
    }
    
    //进行堆排序
    void HeapSort(int A[],int len)
    {
        BuildMaxHeap(A,len);
        for(int i=len;i>1;i--)     //交换根和当前最后一个元素的值
        {
            A[0]=A[i];
            A[i]=A[1];
            A[1]=A[0];
            BuildMaxHeap(A,i-1);   //交换结束后,最大的元素就在最后(就可以忽视它),再使当前数组长度减1,进行堆排序,使最大的元素跑到根节点位置
        }
    }
    
    //打印数组A中的元素
    void PrintfA(int A[],int len)
    {
        for(int i=1;i<=len;i++)
        {
            printf("%d ",A[i]);
        }
        printf("\n");
    }
    
    int main()
    {
        int len=CreateA();
        printf("待排序元素序列为:");
        PrintfA(A,len);
        HeapSort(A,len);
        printf("排序后的元素序列为:");
        PrintfA(A,len);
    }
    

    在这里插入图片描述
    空间效率:O(1)
    时间效率:O(nlog2n)
    稳定性:不稳定

    展开全文
  • 数据结构二叉排序树的实现(用顺序和二叉链表作存储结构)课程设计.pdf
  • 编写排序表的顺序存储形势下经典排序的算法
  • 综述 完整代码-顺序表版本 完整代码-链表版本 交换排序 冒泡排序 ...内排序是指所有的数据已经读入内存,在内存中进行排序的算法。排序过程中不需要对磁盘进行读写。同时,内排序也一般假定所有用...


    先提两个问题:

    1. 插入排序为什么比冒泡常用?
      (两者的最优、平均、最差时间复杂度都相同,且都是原地排序——时间复杂度O(1),并且都是)

    因为冒泡排序的赋值交换次数比插入排序多(插入排序每次交换只需要一次赋值)

    1. 归并的最差时间复杂度比快排低,但是为什么比快排应用更广泛

    因为(没想好)

    如何选择

    • 折半查找:记录数较(但不是海量,数据不分布均匀)
    • 桶排序:数据海量,全量排序,数据分布均匀
    • 快速排序:就平均时间而言,快排是所有排序算法中效果最好的
    • 堆排序:数据,求TopN的场景
    • 基数排序:数据,全量排序,但是数据的范围小,数据可以不均匀(比如高考分数排序)【计数排序也行,但是计数排序处理小数或负数需要扩大范围】
      【再者,比如对100万个手机号码做排序,使用计数排序就不好,使用快排也不好。这时候使用基数排序或者桶排序更佳】
      使用基数排序时,如果数字(或字符串)不等长怎么办?
      在后面补0
    • 直接插入:数据较少,或者数据基本有序
    • 若n较小(如n≤50),可采用直接插入或直接选择排序
    • 若n较大,则应采用时间复杂度为O(nlgn)的排序方法:快速排序、堆排序或归并排序
      快排、冒泡、插入、shell排序,会受到初始序列的影响。

    综述

    排序大的分类可以分为两种:内排序和外排序。

    内排序是指所有的数据已经读入内存,在内存中进行排序的算法。排序过程中不需要对磁盘进行读写。同时,内排序也一般假定所有用到的辅助空间也可以直接存在于内存中。
    外排序即内存中无法保存全部数据,需要进行磁盘访问,每次读入部分数据到内存进行排序。
    这里写图片描述

    时间复杂度和空间复杂度对比表(有必要记忆下)[1]
    这里写图片描述

    完整代码-顺序表版本

    package list;
    
    import java.util.Arrays;
    
    /**
     * <p>Descirption:分别用顺序表以及链表的方式实现常用的几种排序算法</p>
     *
     * @author 王海
     * @version V1.0
     * @package list
     * @date 2018/4/7 16:25
     * @since 1.0
     */
    
    public class MultiSortArrayAndList {
        private static final float[] FORSORT = {10, -2, 3, -1111111111.9999999f, 55, 32.8f, 66, 7.8f, 10233.88f, 52222, 45.67f, 13, 654, 99999, 1000000.666f, 77.77f, 3214, 66, 736.2f, 5, 23, 65465, 54783, 9999.999f, 5664645, -33, -66.5566778899f, 2147483647.555f, 2147483647};
    
        /**
         * 冒泡排序,带标志位(属于交换排序)
         *
         * @param forSort 等待排序的序列
         */
    
        private void bubbleSort(float[] forSort) {
            String name = "冒泡";
            long begin = System.nanoTime();
            if (forSort.length <= 1)  {
            printHelper(name, forSort, begin);
            return;
            }
            // 冒泡排序
            for (int i = 0; i < forSort.length - 1; i++) {
                // 假设下一次不需要再排序
                boolean sorted = false;
                for (int j = 0; j < forSort.length - i - 1; j++) {
                    // 这里-i是因为前几次的排序已经沉底了i个数
                    if (forSort[j] > forSort[j + 1]) {
                        float temp = forSort[j];
                        forSort[j] = forSort[j + 1];
                        forSort[j + 1] = temp;
                        // 排序过了
                        sorted = true;
                    }
                }
                if (!sorted) {
                    break;
                }
            }
            printHelper(name, forSort, begin);
        }
    
        /**
         * 快速排序(属于交换排序)
         *
         * @param forSort 等待排序的序列
         * @param left    左
         * @param right   右
         */
    
        private float[] quickSort(float[] forSort, int left, int right) {
        	if (forSort.length <= 1) return;
            int i = left;
            int j = right;
            // 递归的结束条件
            if (left < right) {
                float benchmark = forSort[left];
                // 下面不能写if,因为并不是说左右指针各移动一次就能保证左右指针“碰头”;完成一次排序
                while (i < j) {
                    // 右侧比较,小则往前放,大则右指针继续“向左前进”
                    while (i < j && forSort[j] > benchmark) {
                        --j;
                    }
                    // while循环退出,如果left还小于right,就该交换数据了
                    if (i < j) {
                        forSort[i++] = forSort[j];
                    }
                    // 左侧比较,大则往后放,小则指针继续“向右前进”
                    while (i < j && forSort[i] < benchmark) {
                        ++i;
                    }
                    if (i < j) {
                        forSort[j--] = forSort[i];
                    }
                }
                forSort[i] = benchmark;
                // 左部分递归
                quickSort(forSort, left, i - 1);
                // 右部分递归(编译器是用栈实现递归,之前的i的状态会“回来”)
                quickSort(forSort, i + 1, right);
            }
            return forSort;
        }
    
        /**
         * 直接排序(属于插入类排序)
         *
         * @param forSort 等待排序的序列
         */
    
        private void driectSort(float[] forSort) {
            String name = "直接插入";
            long begin = System.nanoTime();
            if (forSort.length <= 1)  {
            printHelper(name, forSort, begin);
            return;
            }
            for (int i = 1; i < forSort.length; i++) {
                // 注意,tmp是“准备”本次排序的那个数
                float temp = forSort[i];
                // 第一次j为0,因为第一个数有序
                int j = i - 1;
                while (j >= 0 && temp < forSort[j]) {
                    // 大的先后移
                    forSort[j + 1] = forSort[j];
                    // 没必要马上将当下就位置处的值设为temp,小的继续“往前”
                    --j;
                }
                // j已经小于0了,记得加回去
                forSort[++j] = temp;
            }
            printHelper(name, forSort, begin);
        }
    
        private void shellSort(float[] forSort) {
            String name = "希尔";
            long begin = System.nanoTime();
            if (forSort.length <= 1)  {
            printHelper(name, forSort, begin);
            return;
            }
            // 初始增量increment为length / 2【上下取整都行】
            // 向上取整用Math.ceil()
            // 向下取整用Math.floor(),int a = b/c为下取整
            int incrementNum = forSort.length / 2;
            while (incrementNum >= 1) {
                // 这里的i < forSort.length还不太规范,有多余
                for (int i = 0; i < forSort.length; i++) {
                    // 进行直接插入排序
                    for (int j = i; j < forSort.length - incrementNum; j = j + incrementNum) {
                        int drict = j;
                        // 注意,tmp是“准备”本次排序的那个数
                        float tmp = forSort[drict + incrementNum];
                        while (drict >= 0 && forSort[drict] > forSort[drict + incrementNum]) {
                            forSort[drict + incrementNum] = forSort[drict];
                            drict -= incrementNum;
                        }
                        forSort[drict + incrementNum] = tmp;
                    }
                }
                //设置新的增量
                incrementNum = incrementNum / 2;
            }
            printHelper(name, forSort, begin);
        }
    
        private void binaryInsertSort(float[] forSort) {
            String name = "折半插入";
            long begin = System.nanoTime();
            if (forSort.length <= 1)  {
            printHelper(name, forSort, begin);
            return;
            }
            int n = forSort.length;
            int i, j;
            // "本次"插入数据时,前面已有i个数
            for (i = 1; i < n; i++) {
                // temp为本次循环待插入有序列表中的数
                float tmp = forSort[i];
                int low = 0;
                int high = i - 1;
                // while循环,找到temp插入有序列表的正确位置
                while (low <= high) {
                    // 有序数组的中间坐标,此时用于二分查找,减少查找次数
                    int mid = (low + high) / 2;
                    if (forSort[mid] = tmp) {
                        low = mid;
                        break;
                    }
                    // 若有序数组的中间元素大于待排序元素,则有序序列向中间元素之前搜索,否则向后搜索
                    if (forSort[mid] > tmp) {
                        high = mid - 1;
                    } else {
                        low = mid + 1;
                    }
                }
                for (j = i; j > low; ) {
                    // 从最后一个元素开始,前面的元素依次后移
                    forSort[j] = forSort[--j];
                }
                // 插入temp
                forSort[low] = tmp;
            }
            printHelper(name, forSort, begin);
        }
    
        /**
         * 通用打印方法打印
         *
         * @param sorted    排序好的数组
         * @param sortName  排序方法
         * @param beginTime 排序开始时间
         */
    
        private void printHelper(String sortName, float[] sorted, long beginTime) {
            System.out.println("\n" + sortName + ", 排序耗时=======" + (System.nanoTime() - beginTime) + "纳秒");
            for (float value : sorted) {
                System.out.print(value + "  ");
            }
        }
    
        public static void main(String[] args) {
            for (float aCopy : FORSORT) System.out.print(aCopy + ", ");
    
            MultiSortArrayAndList msort = new MultiSortArrayAndList();
    
    /* 数据量小,比较不出时间 */
    
            // 冒泡排序
            msort.bubbleSort(Arrays.copyOf(FORSORT, FORSORT.length));
            // 快速排序
            long begin = System.nanoTime();
            float[] sorted = msort.quickSort(Arrays.copyOf(FORSORT, FORSORT.length), 0, FORSORT.length - 1);
            System.out.println("\n快速排序, 耗时=======" + (System.nanoTime() - begin) + "纳秒");
            for (float value : sorted) {
                System.out.print(value + "  ");
            }
            // 直接插入
            msort.driectSort(Arrays.copyOf(FORSORT, FORSORT.length));
            // 希尔排序
            msort.shellSort(Arrays.copyOf(FORSORT, FORSORT.length));
            // 折半查找排序
            msort.binaryInsertSort(Arrays.copyOf(FORSORT, FORSORT.length));
    
        }
    }
    

    堆排序(小顶堆增量求topk-海量数据排序)

    package priactice;
    
    import java.util.Arrays;
    
    /**
     * <p>package: priactice</p>
     * <p>
     * descirption:
     *
     * @author 王海
     * @version V1.0
     * @since <pre>2018/9/2 20:01</pre>
     */
    public class HeapSortSmall {
        /**
         * 构建小顶堆(size=10)
         */
        public static void adjustHeap(int[] a, int i, int len) {
            int temp, j;
            temp = a[i];
            for (j = 2 * i + 1; j < len; j = j * 2 + 1) {
                if (j + 1 < len && a[j] > a[j + 1])
                    ++j; // j为较小儿子的下标
                if (temp <= a[j])
                    break;
                a[i] = a[j];
                i = j;
            }
            a[i] = temp;
        }
    
        public static void heapSort(int[] a) {
            // 初始化小顶堆
            int i;
            // 最后一个非叶子节点开始(将其左儿子和右儿子比较)
            for (i = a.length / 2 - 1; i >= 0; i--) {
                adjustHeap(a, i, a.length);
            }
    
            /**
             * 全部读入内存的版本
             */
    //        for (i = a.length - 1; i > 0; i--) {// 将堆顶记录和当前未经排序子序列的最后一个记录交换
    //            int temp = a[0];
    //            a[0] = a[i];
    //            a[i] = temp;
    //            adjustHeap(a, 0, i);// 将a中前i个数重新调整为小顶堆
    //        }
            /**
             * TOP10版本
             */
            int[] ex = {100, 5, 210, 150};
            for (int val : ex) {
                if (val > a[0]) {
                    a[0] = val;
                    adjustHeap(a, 0, a.length);
                }
            }
            //降序
            for (i = a.length - 1; i > 0; i--) {// 将堆顶记录和当前未经排序子序列的最后一个记录交换
                int temp = a[0];
                a[0] = a[i];
                a[i] = temp;
                adjustHeap(a, 0, i);// 将a中前i个数重新调整为小顶堆
            }
        }
    
        public static void main(String[] args) {
            int a[] = {90, 40, 60, 50, 20, 70, 80, 40, 30, 10};
            heapSort(a);
            System.out.println(Arrays.toString(a));
        }
    }
    
    

    完整代码-链表版本

    TODO

    折半查找属于随机访问特性 链表不行
    堆排序也不能用链表 因为调整堆时没法随机访问底层孩子节点
    快速排序、归并排序、基数排序可用链表
    插入排序链表比数组要快一些 减少移动次数
    ##交换排序
    交换类排序的核心是“交换”,每一趟排序,都可能有交换动作。

    冒泡排序

    1.原理:比较两个相邻的元素,每一次都让值大的元素“下沉”,也就是说冒泡排序每一次比较都会交换数据。

    2.时间复杂度:

    • 完全正序时,只需要走一趟即可完成排序(添加一个布尔型标志位)
    • 完全逆序时,则需要进行n-1趟排序。每趟排序要进行n-i次比较(1≤i≤n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较和移动次数均达到最大值:冒泡排序的最坏时间复杂度为:O(n2)

    3.空间复杂度:
    最优的空间复杂度就是开始元素顺序已经排好了,则空间复杂度为:0(不单独使用交换变量的话:a = a + b; b = a - b; a = a - b);
    最差的空间复杂度就是所有元素逆序排序,则空间复杂度为:O(n);
    平均的空间复杂度为:O(1);

    4.思路:需要两层循环,
    外层是遍历每个元素,共需要n-1趟循环;
    内层是相邻数的比较,每趟比较n-趟数。

    快速排序

    1.原理:“分而治之”的思想,围绕“中枢”值分为两部分;需要有前后两个指针(或者说引用),选择一个基准元素(通常是开头或者结尾的元素),对齐进行复制;从末端开始扫描,比被复制的数小的话,将其赋予前面的指针;进行一次赋值后,前指针向后移动,当遇到比被复制的值大的值时,将其赋予后面的指针;对于每一趟的结果,复用上面的方法。
    https://img-blog.csdn.net/20160924234753097

    2.时间复杂度:
    待排序的序列越接近无序,效率越高。
    最坏:最坏情况是指每次区间划分的结果都是基准关键字的左边(或右边)序列为空,即选择的关键字是待排序记录的最小值或最大值。最坏情况下快速排序的时间复杂度为O( n 2 n^2 n2)
    最好:O(n l o g 2 n log_2{n} log2n)

    3.空间复杂度:
    快排需要递归的“辅助”,不是原地排序。递归需要用栈,所以空间复杂度会稍微高些:O( l o g 2 n log_2{n} log2n)

    插入排序

    原序列已经有序,“新来的”需要找准自己的位置。

    直接插入排序

    1.原理:我们从前往后进行排序,一开始只看第一个元素,肯定是有序的。现在插入第二个,与第一个比较,小的往前;接下来第三个元素与第二个元素比较,若大于之,顺序不变,小于之,继续往前比较,直到找到自己的位置。依次类推。

    2.时间复杂度:

    • 最好的情况是,每一次输入的顺序都刚好小于前者,这样就只有一层循环真正起作用,那么复杂度就是O(n)
    • 最坏的情况是,O( n 2 n^2 n2)

    3.空间复杂度:只需要借助一个temp变量,O(1)

    4.思路:
    只需要借助一个temp变量,有需要改变位置的节点时则用,不需要改变位置则节点“原地不动”。

    希尔排序

    1.原理:希尔排序又叫“缩小增量排序”。我们将原始序列按照相同比例分为几个不同的子序列,这个“比例”叫做增量。分别对这些子序列进行直接插入排序增量不断的缩小,直到增量为1,最后综合起来,排序完成。
    希尔排序会造成值相同的元素位置颠倒,所以不稳定。

    2.平均时间复杂度:O(n l o g 2 n log_2{n} log2n)

    3.空间复杂度:O(1)

    4.思路:同原理。

    折半插入排序

    1.原理:折半插入算法是对直接插入排序算法的改进,排序原理同直接插入算法,与直接插入算法的区别在于:在有序表中寻找待排序数据的正确位置时,使用了折半查找/二分查找。

    适合于初始比较有序的序列,但是插入时的比较次数与初始序列无关。

    2.时间复杂度:

    • 最好的情况是,O(n l o g 2 n log_2{n} log2n)
    • 最坏的情况是,O(n),退化为单枝树,查找退化为顺序查找,最坏情况变为O(n)。

    3.空间复杂度:O(1)

    选择排序

    每一趟排序都要选出最小(大)的。

    直接(简单)选择排序

    1.原理:。

    2.时间复杂度:

    • 最好的情况是,那么复杂度就是O(n)
    • 最坏的情况是,O( n 2 n^2 n2)

    3.空间复杂度:O(1)

    4.思路:

    堆排序

    1.概述:
    最终降序,也就是说,要求最大k个数,需要使用小顶堆,当新读入内存的数字大于堆中最小值时,替换掉,重建堆秩序;
    求最小k个数,则相反。
    2.时间复杂度:

    • 最好、平均、最坏都是O(n l o g 2 n log_2{n} log2n)

    3.空间复杂度:O(K):k是初始堆的大小。如果内存能装得下,那就是O(n)

    4.思路:

    归并排序

    1.原理:。

    2.时间复杂度:

    • 最好的情况是,那么复杂度就是O(n)
    • 最坏的情况是,O( n 2 n^2 n2)

    3.空间复杂度:O(1)

    4.思路:

    基数排序

    1.原理:。

    2.时间复杂度:

    • 最好的情况是,那么复杂度就是O(n)
    • 最坏的情况是,O( n 2 n^2 n2)

    3.空间复杂度:O(1)

    4.思路:

    总结

    • **平均性能为O(n^2)的有:**直接插入排序,直接选择排序,冒泡排序
      在数据规模较小时(9W内),直接插入排序,选择排序差不多。
    • **平均性能为O(nlogn)的有:**快速排序,归并排序,堆排序。其中,快排是最好的,其次是归并,堆排序在数据量很大时效果明显(堆排序适合处理大数据)。
    • O(n1+£)阶:£是介于0和1之间的常数,即0<£<1。希尔排序

    **稳定排序:**插入排序,冒泡排序,二叉树排序,归并排序

    不稳定排序:快速排序(快),希尔排序**(些),选择排序(选),堆排序(一堆)**。

    【只需记住一句话(快些选一堆美女)是不稳定的,其他都是稳定的,OK轻松搞定。】

    选择思路:
    因为不同的排序方法适应不同的应用环境和要求,所以选择合适的排序方法应综合考虑下列因素:
      ①待排序的记录数目n;
      ②记录的大小(规模);
      ③关键字的结构及其初始状态;
      ④对稳定性的要求;
      ⑤时间和辅助空间复杂度等;
      ⑥存储结构。

    再次“温习”下稳定性与复杂度:
    这里写图片描述

    “快餐”式温习:
    这里写图片描述

    参考

    [1] 常见排序算法及对应的时间复杂度和空间复杂度
    [2]排序算法性能和使用场景总结

    数据结构复习之顺序表以及链表的方式实现常用的几种排序算法
    [3] 白话经典算法系列之六 快速排序 快速搞定

    展开全文
  • /*修改本程序,对顺序表进行冒泡排序,使其有序*/ #define MAXSIZE 100 /*宏定义*/ #define OK 1 #define OVERFLOW -2 #include "stdio.h" /*包含输入输出文件*/ typedef int elemtype; typedef struct /*定义顺序...
  • 数据结构-基于C语言实现线性顺序表的增删改查+排序,合表操作
  • 二叉树的存储结构有两种,分别为顺序存储和链式存储
  • 如果不排序数据一般将它底层表现中出现的顺序显示。这可以是数据最初添加到表中的顺序。但是,如果数据后来进行过更新或删除,则此顺序将会受到MySQL重用回收存储空间的影响。因此,如果不明确控制的话,不能...
  • 线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素,使得线性表中在逻辑结构上相邻的数据元素存储在连续的物理存储单元中,即通过数据元素物理存储的连续性来反映数据元素之间逻辑上的相邻...
  • #include <iostream> using namespace std; #define MAXSIZE 100 //顺序表的最大长度 typedef struct { int key; char *otherinfo; }ElemType;...//顺序表的存储结构 typedef st...
  • 2.用顺序表(一维数组)作存储结构 (1)回车('\n')为输入结束标志,输入数列L,生成一棵二叉排序树T; (2)对二叉排序树T作中序遍历,输出结果; (3)计算二叉排序树T查找成功的平均查找长度,输出结果; (4)输入元素...
  • 数据结构——顺序存储二叉树

    千次阅读 2020-05-15 11:15:19
    八大排序算法中的堆排序,就会使用到顺序存储二叉树,后面在堆排序算法中会体现出来。 1. 什么叫作顺序存储二叉树 当一颗二叉树满足如下两个条件时,就是顺序存储二叉树: 二叉树是数组的方式存放数据的。如下图...
  • mysql排序数据

    千次阅读 2021-01-25 17:26:58
    介绍当使用SELECT语句查询表中的数据时,结果集不按任何顺序进行排序。要对结果集进行排序,请使用ORDER BY子句。ORDER BY子句允许:对单个列或多个列排序结果集。按升序或降序对不同列的结果集进行排序。使用方式:...
  • 顺序储存数据时,会提前申请一整块足够大小的物理空间,然后将数据依次储存起来,储存时做到数据元素之间不留一丝缝隙。 顺序表_百度百科 个人理解:顺序储存数据的模式同数组十分相近,但是(当然有但是,...
  • 数据库保存数据顺序问题

    千次阅读 2021-02-05 04:40:35
    需求:依次采集excel中的每行记录存入数据库,然后从数据库获取记录的时候不能改变原有excel中数据顺序。例如:excel中存的记录顺序是1,2,3。从数据库取出来也得是1,2,3。过程:本来在数据库比较闲的时候这...
  • 如何在数据库中存储顺序数据

    千次阅读 2021-01-28 05:46:26
    如果在实际应用中,我们需要在数据库中存储类似于列表的有顺序数据,此时该采取怎样的策略呢?一种直接而有效的方法是,在记录集(或表)中增加一个“顺序”列(或叫“索引”字段),对表进行存入、取出或者排序的操作...
  • 数据结构查找--顺序表的顺序查找

    千次阅读 2021-11-20 19:49:26
    顺序查找:从表的一端开始,依次将记录在表中的关键字与给定值进行比较,若某个记录的关键字和给定值相同,则查找成功;反之查找失败。 顺序查找既适用于顺序表,又适用于线性表,首先先介绍顺序表中的顺序查找 ...
  • 之前的文章,我已经把前端需要了解的...现在我们要开始对排序算法部分进行讲解,排序算法顾名思义,就是对一堆杂乱无章的数据按照一定的规则将它们有序地排列在一起。 在讲解排序算法时,大致分成两大类,如下图 本文
  • 定义一个包含图书信息(书号、书名、价格)的顺序表,读入相应的图书数据完成图书信息表的创建,然后将图书按照价格降序排序,逐行输出排序后每本图书的信息。 输入 输入n+1行,前n行是n本图书的信息(书号、书名、...
  • mysql实现按照自定义(指定顺序排序

    万次阅读 多人点赞 2022-01-31 17:50:35
    mysql实现自定义排序
  • JSONObject数据排序顺序)问题

    万次阅读 多人点赞 2018-01-22 10:18:21
    JSONObject内部是用Hashmap来存储的,所以输出是按key的ASCII码排序来的,如果要让JSONObject按固定顺序(put的顺序)排列,可以修改JSONObject的定义HashMap改为LinkedHashMap。 publicJSONObject(){ this.map=...
  • 数据结构-快速排序(含全部代码)

    万次阅读 2021-03-15 17:09:19
    L,int low,high) 参数:顺序表L,待排最小下标,待排最大下标 功能:排序(默认升序)空间复杂度:O(1) 时间复杂度:O(nlog2n)-O(n) 稳定性:不稳定 代码 //快速排序分割函数 int Partition(SqList &L,int ...
  • “具有 ‘一对一’ 逻辑关系的数据按照次序连续存储到一整块物理空间上”的存储结构就是顺序存储结构。   我们就可以把线性表的顺序存储理解为是数组的拓展,物理空间上都是依次连续的这样一种用于存储数据的结构...
  • 数据结构之顺序文件

    千次阅读 2022-04-20 15:49:23
    顺序文件(Sequential File)是记录按其在文件中的逻辑顺序依次进入存储介质而建立的,即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。若次序相继的两个物理记录在存储介质上的存储位置是相邻的,则又称连续文件;...
  • 22计算机408考研—数据结构—排序(详解加例题)

    万次阅读 多人点赞 2021-09-20 14:29:19
    顾名思义,给一个无序数组的值进行顺序存储 原数组:2 3 1 5 6 4 8 9 7 排序后:1 2 3 4 5 6 7 8 9 直接插入排序 思路: 插入 == 把数插进去 也是两层循环 数组num 第一层循环从下标为1的值开始,循环变量为i 第二...
  • MySQL--排序检索数据(ORDER BY)

    千次阅读 2021-01-27 10:30:11
    检索出的数据并不是纯粹的随机顺序显示的。如果不排序,数据一般将它在底层表中出现的顺序显示。这可以是数据最初添加到表中的顺序。但是,如果数据后来进行过更新或删除,则此...1、排序数据SELECTprod_name...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 448,615
精华内容 179,446
热门标签
关键字:

内排序要求数据一定以顺序方式存储

友情链接: adder.zip