精华内容
下载资源
问答
  • 十大排序、七大查找算法python实现——选择排序(selection sort) 原理参考链接:https://www.cnblogs.com/onepixel/articles/7674659.html 选择排序的原理是,在无序数组找到最小或最大的元素,然后将其移动至...

    十大排序、七大查找算法python实现——选择排序(selection sort)

    原理参考链接:https://www.cnblogs.com/onepixel/articles/7674659.html

     

    选择排序的原理是,在无序数组中找到最小或最大的元素,然后将其移动至无序数组的最右或最左边,逐渐形成有序数组。具体实施步骤如下:

    • 初始状态:无序区为R[1..n],有序区为空;
    • 第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;
    • n-1趟结束,数组有序化了。
    def selection_sort(L):
        n = len(L)
        
        for i in range(n-1):  # 执行n-1次
            min_index = i  #  获取无序数组的第一个元素的下标
            for j in range(i+1, n):  # 扫描无序数组中最小的元素
                if L[min_index] > L[j]:
                    min_index = j  # 返回最小元素的下标
            if i != min_index:
                L[min_index], L[i] = L[i], L[min_index] # 将最小元素与无序数组的第一个元素交换位置
            print(L)
        return

    执行结果如下,我们可以看到,随着算法的不断执行,右侧无序数组中的最小元素逐渐移向左侧位置。

    展开全文
  • 题目描述 ...先利用sort函数排序,第一个元素查找到中间元素,如果存在相隔数组长度一半及以上位置的元素相等的话(好难描述…),判定成功,返回该元素。这个方法操作比较麻烦,需要考虑数组...

    题目描述

    数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0

    方法一

    先利用sort函数排序,从第一个元素查找到中间元素,如果存在相隔数组长度一半及以上位置的元素相等的话(好难描述…),判定成功,返回该元素。这个方法操作比较麻烦,需要考虑数组左右,并且需要考虑数组的长度奇偶。

    牛客AC代码如下

    import java.util.Arrays;
    public class Solution {
        public int MoreThanHalfNum_Solution(int [] array) {
             
             
            int temp=0;
            if(array.length==0||array==null){
                return 0;
            }else if(array.length==1)
                return temp=array[0];
             else if(array.length==2&&array[0]!=array[1])
                 return temp=0;
            else{
                Arrays.sort(array);
                for (int i = 0; i < array.length/2; i++) {
                    if(array[i]==array[array.length-1-i] || (array[i]==array[array.length/2]&&array.length%2==0))
                         temp=array[i];
                    if(array[array.length/2]==array[array.length-1] && array.length%2!=0)
                        temp=array[array.length/2];
                }
                return temp;
            }
             
                 
             
             
         
        }
    }
    
    

    方法二

    建立一个count方法统计数组中每个元素出现的次数num,并返回。在判定方法里调用count方法,如果num大于数组长度一半,判定成功。这个方法不需要考虑数组奇偶,比较好理解。

    牛客AC代码如下

    import java.util.Arrays;
    public class Solution {
            private int count(int x,int[] array) {
    		// TODO 自动生成的方法存根
    		int num=0;
    		for (int i = 0; i < array.length; i++) {
    			if(x==array[i])
    				num++;
    		}
    		
    		return num;
    
    	}
    public int MoreThanHalfNum_Solution(int [] array) {
    	int num=0;
    	for (int i = 0; i < array.length; i++) {
    		if(count(array[i], array)>array.length/2){
    			num=array[i];
    		}
    			
    		
    	}
    	return num;
    	
    	
    	
    } 
    }
    
    展开全文
  • 常用排序汇总

    2020-04-15 11:53:13
    查找出arr(i)在L[1…i-1]的插入位置k 将arr[k…i-1]所有元素全部后移一个位置 将arr(i)复制到arr(k) void insertionSort( T arr[], int n){ //插入排序 for(int i = 1; i < n; i++){ //插入排序i= 1开始...

    语法简单说明

    using namespace std;
    template <typename T>
    

    插入排序InsertionSort

    • 查找出arr(i)在L[1…i-1]中的插入位置k
    • 将arr[k…i-1]中所有元素全部后移一个位置
    • 将arr(i)复制到arr(k)
    void insertionSort( T arr[], int n){    //插入排序
        for(int i = 1; i < n; i++){    //插入排序从i= 1开始,因为第一个元素从一开始就已经有序了
            //寻找元素arr[i]合适的插入位置
    //        for(int j = i; j>0; j--)  //循环到最后j=1,判断与j=0位置的元素是否交换,相对于选择排序,第二层循环会提前结束
    //            if( arr[j] <  arr[j-1])
    //                swap(arr[j], arr[j-1]);
    //            else
    //                break;
    //或者采用下面的方法,将判断放在for循环中
    //        for(int j = i; j>0&&arr[j] <arr[j-1];j--){
    //            swap(arr[j],arr[j-1]);
    //        }
            //经过优化后的代码
            T e = arr[i];
            int j;    //j保存元素e应该插入的位置
            for(j = i; j>0 && arr[j-1] > e; j--){
                arr[j] = arr[j-1];    //把j-1位置的元素向后挪一下
            }
            arr[j] = e;
        }
    }
    
    #插入排序Python版
    def insertion_sort(a):
        for i in range(1,len(a)):
            cur = a[i]
            j = i
            while j>0 and a[j-1]>cur:
                a[j] = a[j-1]
                j -= 1
            a[j] = e
        return a
    

    选择排序SelectionSort

    版本一
    void selectionSort( T arr[], int n){    //选择排序
        for(int i = 0; i < n; i++){
            //寻找[i, n)区间的最小值
            int minIndex = i;
            for( int j = i+1; j<n;j++)
                if(arr[j] < arr[minIndex])
                    minIndex = j;
            swap( arr[i], arr[minIndex]);  // C++标准库
        }
    }
    
    版本二,优化

    在每一轮中, 可以同时找到当前未处理元素的最大值和最小值

    void selectionSort(T arr[], int n){
    
        int left = 0, right = n - 1;
        while(left < right){
            int minIndex = left;
            int maxIndex = right;
            // 在每一轮查找时, 要保证arr[minIndex] <= arr[maxIndex]
            if(arr[minIndex] > arr[maxIndex])
                swap(arr[minIndex], arr[maxIndex]);
    
            for(int i = left + 1 ; i < right; i ++)
                if(arr[i] < arr[minIndex])
                    minIndex = i;
                else if(arr[i] > arr[maxIndex])
                    maxIndex = i;
    
            swap(arr[left], arr[minIndex]);
            swap(arr[right], arr[maxIndex]);
    
            left ++;
            right --;
        }
    
        return;
    }
    
    #直接选择排序Python版
    def selection_sort(a):
        for i in range(len(a)-1):
            min_index = i
            for j in range(i+1, len(a)):
                if a[j]<a[min_index]:
                    min_index = j
            if i != min_index:
                a[i], a[min_index] = a[min_index], a[i]
        return a
    

    希尔排序ShellSort

    void shellSort(T arr[], int n){
         // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...
        int h = 1;
        while(h < n/3)
            h = 3 * h + 1;    //取一个步长
    
        while(h >= 1){
            for( int i = h; i <n ; i++){
                //对arr[i], arr[i-h], arrr[i-2*h], arr[i-3*h]...使用插入排序
                T e = arr[i];
                int j;
                for( j=i; j >= h&& e<arr[j-h]; j-=h)
                    arr[j] = arr[j-h];     //从后往前寻找插入位置
                arr[j]=e;
            }
            h/=3;
        }
    }
    

    冒泡排序BubbleSort

    版本一
    void bubbleSort( T arr[] , int n){
        bool swapped;
        do{
            swapped = false;
            for( int i = 1 ; i < n ; i ++ )
                if( arr[i-1] > arr[i] ){
                    swap( arr[i-1] , arr[i] );
                    swapped = true;
                }
            // 优化, 每一趟Bubble Sort都将最大的元素放在了最后的位置
            // 所以下一次排序, 最后的元素可以不再考虑
            n --;
        }while(swapped);
    }
    
    版本二
    // 我们的第二版bubbleSort,使用newn进行优化
    template<typename T>
    void bubbleSort2( T arr[] , int n){
    
        int newn; // 使用newn进行优化
        do{
            newn = 0;
            for( int i = 1 ; i < n ; i ++ )
                if( arr[i-1] > arr[i] ){
                    swap( arr[i-1] , arr[i] );
                    // 记录最后一次的交换位置,在此之后的元素在下一轮扫描中均不考虑
                    newn = i;
                }
            n = newn;
        }while(newn > 0);
    }
    
    #冒泡排序
    def bubble_sort(a, n):
        ac = a.copy()
        swap_size = 1
        while swap_size > 0:
            swap_size = 0
            for i in range(n-1):
                if ac[i] > ac[i+1]:
                    ac[i], ac[i+1] = ac[i+1], ac[i]
                    swap_size += 1
            n -= 1
        return ac
    

    快速排序QuickSort

    // 对arr[l...r]部分进行快速排序
    template <typename T>
    void __quickSort(T arr[], int l, int r){
    
        if( l >= r )
            return;
        int p = __partition(arr, l, r);
        __quickSort(arr, l, p-1 );
        __quickSort(arr, p+1, r);
    }
    
    版本一,双路
    int __partition2(T arr[], int l, int r){    //双路快速排序
    
        swap(arr[l], arr[rand()%(r-l+1)+l]);
        T v = arr[l];
    
        //arr[l+1...i) <= v;  arr(j...r] >= v
        int i = l+1, j = r;
        while(true){
            while(i <=r && arr[i] <v) i++;
            while(j >= l+1 && arr[j] > v) j--;
            if( i> j) break;
            swap( arr[i], arr[j] );
            i++;
            j--;
        }
        swap(arr[l], arr[j]);
        return j;
    }
    
    版本二 ,三路
    // 递归的三路快速排序算法
    template <typename T>
    void __quickSort3Ways(T arr[], int l, int r){
    
        // 对于小规模数组, 使用插入排序进行优化
        if( r - l <= 15 ){
            insertionSort(arr,l,r);
            return;
        }
    
        // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
        swap( arr[l], arr[rand()%(r-l+1)+l ] );
    
        T v = arr[l];
    
        int lt = l;     // arr[l+1...lt] < v
        int gt = r + 1; // arr[gt...r] > v
        int i = l+1;    // arr[lt+1...i) == v
        while( i < gt ){
            if( arr[i] < v ){
                swap( arr[i], arr[lt+1]);
                i ++;
                lt ++;
            }
            else if( arr[i] > v ){
                swap( arr[i], arr[gt-1]);
                gt --;
            }
            else{ // arr[i] == v
                i ++;
            }
        }
    
        swap( arr[l] , arr[lt] );
    
        __quickSort3Ways(arr, l, lt-1);
        __quickSort3Ways(arr, gt, r);
    }
    
    template <typename T>
    void quickSort3Ways(T arr[], int n){
    
        srand(time(NULL));
        __quickSort3Ways( arr, 0, n-1);
    }
    

    合并排序MergeSort

    void MergeSort(T A[], int low, int high){
        if(low < high){
            int mid = (low+high)/2;  //从中间划分两个子序列
            MergeSort(A, low, mid);  //对左侧子序列进行递归排序
            MergeSort(A, mid, high);
            Merge(A, low, mid, high); //归并
        }
    }
    
    void Mereg( T A[], int low, int mid, int high){
        //表A的两段A[low...mid]和A[mid+1...high]各自有序,将他们合成一个有序表
        T B[high-low+1];
        for (int k = low; k < high; ++k) 
            B[k] = A[k];
        for (int i=low, j=mid+1, k=i; i<=mid && j<=high ; k++) {
            if(B[i] <= B[j])
                A[k] = B[i++];
            else
                A[k] = B[j++];
        } //for
        
        while(i<=mid) A[k++] = A[i++];  //若左半部分未检测完,复制
        while(j<=high) A[k++] = A[j++];
    }
    

    堆排序

    //创建一个大根堆
    void BuildMaxHeap(T A[], int len){
        for (int i = len/2; i > 0; i--)
            AdjustDown(A, i, len);
    }
    
    void shiftUp(int k){               
        while( k>1 && data[k/2] < data[k]){   
            swap(data[k/2], data[k]);
            k /= 2;
        }
    }
    
    void AdjustDown(T A[], int k, int len){
        //将元素k向下调整
        T e = A[k];
        for (int i = 2*k; i <= len; i*=2) {
            if(i<len&&A[i]<A[i+1])
                i++;
            if(e>=A[i]) break;
            else{
                A[k] = A[i];
                k=i;
            }
        }
        A[k] = e;
    }
    
    void HeapSort(T A[], int len){
        BuildMaxHeap(A, len);     //初始建堆
        for (int i = len; i > 1 ; i--) {
            Swap(A[i], A[1]);    // 输出堆顶元素(和堆底元素进行交换)
            AdjustDown(A, 1, i-1);  //剩余i-1个元素整理成堆
    
        }
    }
    
    展开全文
  • 服务器上传文件失败了,才.../ //在整个系统(根目录开始)中查找 -type //指定文件类型 f //普通文件 -print0 //在标准输出显示完整的文件名,其后跟一个空字符(null) | //控制操作符,将一条命令的输出传递给下一

    服务器上传文件失败了,才开始没考虑到磁盘原因还以为是自己的scrt的问题,还好df -h看了下,最后发现磁盘满了,真是…

    find / -type f -print0 | xargs -0 du -h | sort -rh | head -n 10
    详解

    find //在目录结构中搜索文件的命令
    / //在整个系统(从根目录开始)中查找
    -type //指定文件类型
    f //普通文件
    -print0 //在标准输出显示完整的文件名,其后跟一个空字符(null)
    | //控制操作符,将一条命令的输出传递给下一个命令以供进一步处理
    xargs //将标准输入转换成命令行参数的命令
    -0 //以空字符(null)而不是空白字符(LCTT 译者注:即空格、制表符和换行)来分割记录
    du -h //以可读格式计算磁盘空间使用情况的命令
    sort //对文本文件进行排序的命令
    -r //反转结果
    -h //用可读格式打印输出
    head //输出文件开头部分的命令
    n -10 //打印前 10 个文件

    展开全文
  • 实例035 字符串分离文件路径、文件名及扩展名 51 实例036 对字符串进行加密与解密 53 实例037 开发一个进制转换器 56 实例038 将字符串的每个字符进行颠倒输出 60 实例039 根据标点符号对字符串进行分行 61 实例...
  • 实例078 字符串分离文件路径、文件名及扩展名 实例079 判断手机号的合法性 实例080 用字符串构建器追加字符 实例081 去掉字符串的所有空格 实例082 汉字与区位码的转换 第5章 面向对象技术应用 5.1 ...
  • 实例078 字符串分离文件路径、文件名及扩展名 实例079 判断手机号的合法性 实例080 用字符串构建器追加字符 实例081 去掉字符串的所有空格 实例082 汉字与区位码的转换 第5章 面向对象技术应用 5.1 ...
  • 实例245 在ListBox控件中查找指定项 实例246 将数据库数据添加到组合框中 实例247 在ListBox控件间交换数据 实例248 借助绑定控件实现数据选择录入 11.6 ListView控件应用 实例249 ListView控件间的数据移动 ...
  • 实例245 在ListBox控件中查找指定项 实例246 将数据库数据添加到组合框中 实例247 在ListBox控件间交换数据 实例248 借助绑定控件实现数据选择录入 11.6 ListView控件应用 实例249 ListView控件间的数据移动 ...
  • 实例245 在ListBox控件中查找指定项 实例246 将数据库数据添加到组合框中 实例247 在ListBox控件间交换数据 实例248 借助绑定控件实现数据选择录入 11.6 ListView控件应用 实例249 ListView控件间的数据移动 ...
  •  实例043 字符串分离文件路径、文件名及扩展名 55  实例044 获取字符串汉字的个数 57  实例045 批量替换某一类字符串 58  实例046 对字符串进行加密与解密 59 3.3 常用数字处理技术 61  实例047 ...
  • 实例043 字符串分离文件路径、文件名及 扩展名 55 实例044 获取字符串汉字的个数 57 实例045 批量替换某一类字符串 58 实例046 对字符串进行加密与解密 59 3.3 常用数字处理技术 61 实例047 判断输入的货币值...
  • 实例078 字符串分离文件路径、 文件名及扩展名 98 实例079 判断手机号的合法性 99 实例080 用字符串构建器追加字符 100 实例081 去掉字符串的所有空格 101 实例082 汉字与区位码的转换 102 第5章 面向对象技术...
  • 实例078 字符串分离文件路径、 文件名及扩展名 98 实例079 判断手机号的合法性 99 实例080 用字符串构建器追加字符 100 实例081 去掉字符串的所有空格 101 实例082 汉字与区位码的转换 102 第5章 面向对象技术...
  • Java经典编程300例(code)

    千次下载 热门讨论 2013-01-09 10:26:53
    实例172 在压缩文件中查找字符串 238 实例173 重命名RAR压缩包中文件 239 实例174 创建自解压RAR压缩包 240 第13章 枚举类型与泛型 242 实例175 查看枚举类型的定义 243 实例176 枚举类型的基本特性 244 实例177 ...
  •  10.4.1 使用sort()算法对容器的数据进行排序  10.4.2 对排序的规则进行自定义  10.5 实战STL算法  10.5.1 “算法”老师带来的一堂别开生面的体育课  10.5.2 删除容器的冗余元素  第11章 函数指针、函数...
  • 《数据结构 1800题》

    热门讨论 2012-12-27 16:52:03
    10. 在顺序存储结构,有时也存储数据结构元素之间的关系。( )【华南理工大学 2002 一、2 (1分)】 11. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。( )【上海海运学院 1999 一、1(1分)】 12....
  • (8)编写一个程序实现如下功能:字符串删除指定的字符。同一字母的大、小写按不同字符处理。 例:若程序执行时,输入字符串为:Shanghai Dianji University,键盘上输入字符:s,则输出后变为:Shanghai ...
  • C#全能速查宝典

    热门讨论 2014-04-26 16:16:27
    1.1.3 base关键字——派生类访问基类的成员 3 1.1.4 变量——存储特定类型的数据 4 1.1.5 Console类——控制台的输入流、输出流和错误流 6 1.1.6 Convert类——类型转换 8 1.1.7 常量——值不改变的量 9 1.1.8...
  • 9.8将一个5×5的矩阵最大的元素放在中心,4个角分别放在4个最小的元素(按左到右,上到下的顺序,依次从小到大存放),写一个函数实现之,并用main函数调用。 78 10.9在主函数输入10个等长的字符串。用另一...
  • 数据结构演示软件

    2013-06-02 21:32:36
    本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法执行过程数据的逻辑结构或存储结构的变化状况或递归算法执行...
  • 本课件是一个动态演示数据结构算法执行过程的辅助教学软件, 它可适应读者对算法的输入数据和过程执行的控制方式的不同需求, 在计算机的屏幕上显示算法执行过程数据的逻辑结构或存储结构的变化状况或递归算法执行...
  •  可能你还需要查询一些Unix/Linux命令,比如awk,、sort、tr、cut、paste、sed、grep;你也可能还需要查询其他的Unix/Linux命令。  建议你在主目录下建立一个以 xx xx xx(xx xx xx为学号)命名的目录,并且在本次...
  • <ul><li>集合必存在唯一的一个“第一个元素”</li><li>集合必存在唯一的一个“最后的元素”</li><li>除最后一元素之外,其它数据元素均有唯一的“后继”</li><li>除第一个元素之外,其它数据元素均...

空空如也

空空如也

1 2
收藏数 24
精华内容 9
关键字:

从…中查找sort