精华内容
下载资源
问答
  • 主要介绍了C语言 数据结构堆排序顺序存储(升序)的相关资料,需要的朋友可以参考下
  • 非常棒的数据结构程序演示 ,分为Pascal语言和C语言版,其中包含 顺序表 广义表 动态查找 静态查找 二叉树 链表 栈 串 稀疏矩阵 储存管理 内部排序 外部排序等等 只需解压即可
  • 编写排序表的顺序存储形势下经典排序的算法
  • 直接插入排序顺序存储、链式存储),折半插入排序顺序存储),希尔排序顺序存储) 插入排序 直接插入排序 将元素插入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);
    }
    

    在这里插入图片描述

    展开全文
  • 综述 完整代码-顺序表版本 完整代码-链表版本 交换排序 冒泡排序 ...内排序是指所有的数据已经读入内存,在内存中进行排序的算法。排序过程中不需要对磁盘进行读写。同时,内排序也一般假定所有用...


    先提两个问题:

    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] 白话经典算法系列之六 快速排序 快速搞定

    展开全文
  • JSONObject数据排序顺序)问题

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

    JSONObject内部是用Hashmap来存储的,所以输出是按key的ASCII码排序来的,如果要让JSONObject按固定顺序(put的顺序)排列,可以修改JSONObject的定义HashMap改为LinkedHashMap。

    public JSONObject() {  
            this.map = new LinkedHashMap();  //new HashMap();  
    }  

    即定义JSONObject可以这样:JSONObject jsonObj = new JSONObject(new LinkedHashMap());

    或者 JSONObject jsonObj = new JSONObject(true);

    展开全文
  • 顺序方式排序存储的文件,怎么使用二分法进行检索?检索前必须对数据进行排序么?那么排序过程中如果有新的数据怎么办?
  • JsonObject数据排序顺序)问题

    万次阅读 2018-03-21 17:50:07
    JsonObject内部是用Hashmap来存储的,所以输出是按key的排序来的,如果要让JsonObject按固定顺序(put的顺序)排列,可以修改JsonObject的定义HashMap改为LinkedHashMap。public JSONObject() { this.map = new...

    JsonObject内部是用Hashmap来存储的,所以输出是按key的排序来的,如果要让JsonObject按固定顺序(put的顺序)排列,可以修改JsonObject的定义HashMap改为LinkedHashMap

    public JSONObject() {  
            this.map = new LinkedHashMap();  //new HashMap();  
    }  

    即定义JsonObject可以这样:JSONObject jsonObj = new JSONObject(new LinkedHashMap());

    展开全文
  • //查找排序(顺序查找)一个表长100的顺序存储表,要求使用顺序查找列表中的元素并输出 #include #define SIZE 150  //100长度 typedef int Datatype; struct Seqlist {   Datatype data...
  • 定义一个包含图书信息(书号、书名、价格)的顺序表,读入相应的图书数据完成图书信息表的创建,然后将图书按照价格降序排序,逐行输出排序后每本图书的信息。 输入 输入n+1行,前n行是n本图书的信息(书号、书名、...
  • Ø 理解并实现选择排序,冒泡排序,合并排序,快速排序,插入排序和shell排序 Ø 理解哈希表用于查找的技术 Ø 介绍映射的抽象数据类型 Ø 用哈希表实现映射的抽象数据类型 查找 现在我们转向排序...
  • 数据结构-顺序表基本操作的实现(含全部代码)

    万次阅读 多人点赞 2018-09-13 22:14:57
    今天起开始编写数据结构中的各种数据结构及其算法的实现。 主要依据严蔚敏版数据结构教材以及王道数据结构考研辅导书。 今天是线性表中的顺序表的实现,主要实现函数如下,读者有需要可以评论,我可以适当加几个。...
  • 排序顺序存储

    千次阅读 2016-10-29 13:19:39
    排序顺序存储(升序) ㈠ 完全二叉树的概念:前h-1层为满二叉树,最后一层连续缺失右结点! ㈡ 首先堆是一棵全完二叉树: a:构建一个堆分为两步: ⑴创建一棵完全二叉树 ⑵调整为一个堆 (标注:大根堆为升序,...
  • 顺序存储在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。特点:随机存取表中元素。插入和删除操作需要移动元素。链接存储在计算机中用一组任意的存储单元存储线性表的...
  • 冒泡排序应用——顺序排序

    千次阅读 2017-04-17 23:12:07
    * 冒泡排序应用——顺序排序 */ #include using namespace std;#define MAXSIZE 20 //顺序表的最大长度typedef struct { int key; char *otherinfo; }ElemType;//顺序表的存储结构 typedef struct
  • cout数据输出\n"; for(i=1; i; i++) cout[i].key; cout结束显示"; } template<class T>void bubblesort(T r[], int n) { int i=1,tag,m; T x; do { tag = 0; x = r[i]; for(int j=n;j>i;j--) { if(r[j...
  • 我们经典的排序有内部排序和外部排序,内部排序数据记录在内存中进行排序,而外部排序是因排序数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 算法复杂度如下图: 下面我们一一来总结...
  • (1)用顺序表作为通讯录的存储结构。每条通讯录包含:姓名,城市,电话。表中的记录按姓名非递减有序,每插入一条记录后,应使表中记录仍保持按姓名非递减排序。 (2)实现插入、删除、修改、显示、查找功能(插入...
  • 数据结构课程设计 用顺序和二叉链表作存储结构实现二叉排序
  • 数据结构之顺序查找

    千次阅读 2019-08-09 21:38:22
    排序直接的数据结构介绍; 顺序查找和折半查找是顺序存储;二叉排序树是二叉树存储;哈希查抄是类图(和图的邻接表存储相似); 头文件(Search.h); # ifndef _SORT_ typedef int KeyType; typedef ...
  • 在查询一个表的数据时发现查询返回的数据中_id 字段的值的排序是乱的。并没有 按整数数据进行排序,这里做一些说明:     在MONGODB 中,如果没有加sort,返回的是数据原始存储顺序,和下面的代码一致:   ...
  • #include <iostream> using namespace std; #define MAXSIZE 100 //顺序表的最大长度 typedef struct { int key; char *otherinfo; }ElemType;...//顺序表的存储结构 typedef st...
  • 定义一个包含图书信息(书号、书名、价格)的顺序表,读入相应的图书数据完成图书信息表的创建,然后将图书按照价格降序排序,逐行输出排序后每本图书的信息。 输入描述 输入n+1 行,前n 行是n 本图书的信息(书号、...
  • 数据结构排序算法系列】数据结构八大排序算法

    万次阅读 多人点赞 2016-03-25 22:36:40
    如Windows操作系统的文件管理中会自动对用户创建的文件按照一定的规则排序(这个规则用户可以自定义,默认按照文件名排序)因此熟练掌握各种排序算法是非常重要的,本博客将对数据结构中常见的八大排序算法进行详细...
  • 排序数据依赖性

    千次阅读 多人点赞 2019-10-04 15:14:07
    上一篇博客我们了解了Java内存模型,下面我们来了解一下重排序数据依赖性的相关知识。 为什么需要重排序 现在的CPU一般采用流水线来执行指令。一个指令的执行被分成:取指、译码、访存、执行、写回、等若干个阶段...
  • 1.python实现:对若干学生一门课成绩进行排序要求数据输入,排序、输出分别用函数实现 请关注【python的爬虫与数据分析之路】gzh,回复‘作业’获取答案
  • 数据结构排序

    2020-12-05 18:01:37
    文章目录八、排序8.1、基本概念和排序方法概述8.1.1、排序的基本概念8.1.2、内部排序方法的分类8.1.3、待排序记录的存储方式8.2、插入排序8.2.1、直接插入排序   整本书的知识点,点击右方链接:整本书笔记...
  • JsonObject数据顺序问题

    千次阅读 2019-04-10 13:26:08
    在生成json的时候,发现JsonObject不能按put顺序显示数据,查看了一下JsonObject类,发现JsonObject内部是用Hashmap来存储的,所以输出是按key的排序来的,如果要让JsonObject按put的先后顺序排列,可以修改...
  • 顺序存储(顺序表)

    万次阅读 多人点赞 2018-08-25 11:56:23
    线性表的顺序存储结构,就是在内存中找到一块空间,通过占位的方式,把一定内存空间给占了,然后把相同数据类型的数据元素依次存放在这块空间中,既然线性表的每个数据元素的类型相同,所以C语言(其他语言也相同)...
  • 八大排序算法

    万次阅读 多人点赞 2012-07-23 16:45:18
    排序有内部排序和外部排序,内部排序数据记录在内存中进行排序,而外部排序是因排序数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里说说八大排序就是内部排序。 当n较大,则...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 384,213
精华内容 153,685
关键字:

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