首页 > 试题广场 >

排序

[编程题]排序
  • 热度指数:303853 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一个长度为 n 的数组,请你编写一个函数,返回该数组按升序排序后的结果。

数据范围: ,数组中每个元素都满足
要求:时间复杂度 ,空间复杂度
进阶:时间复杂度 ,空间复杂度

注:本题数据范围允许绝大部分排序算法,请尝试多种排序算法的实现。
示例1

输入

[5,2,3,1,4]

输出

[1,2,3,4,5]
示例2

输入

[5,1,6,2,5]

输出

[1,2,5,5,6]
按照标准快速排序的前后指针法,即选取最左侧元素为基准,用一个pre指针和 cur指针均指向起始位置,依次移动cur指针向右遍历。若arr[cur]的值大于等于base,右移cur;若小于base,则向右移pre,并将pre移动后所指的元素与cur所指的进行交换,交换后cur所指的元素必定是大于等于base的值,所以还需右移cur。最后,再交换base与pre所指的元素。

双指针的原理是,确保从左至pre均为小于base的值,从pre到cur所指的均为大于等于base的值。
编写代码如下:
class Solution:
    def partition(self, arr, l, r) -> int:
        base = arr[l]
        pre = l
        cur = l + 1
        while cur <= r:
            if arr[cur] < base:
                pre += 1
                arr[pre], arr[cur] = arr[cur], arr[pre]
            cur += 1
        arr[l], arr[pre] = arr[pre], arr[l]
        return pre

    def inner_sort(self, arr, l, r):
        if l >= r:
            return arr
        mid = self.partition(arr, l, r)
        self.inner_sort(arr, l, mid - 1)
        self.inner_sort(arr, mid + 1, r)
        return arr

    def MySort(self , arr: List[int]) -> List[int]:
        # write code here
        return self.inner_sort(arr, 0, len(arr) - 1)
由于是递归调用,最终不能通过:
"6/8 组用例通过
RecursionError: maximum recursion depth exceeded in comparison"
改动“inner_sort”函数,借用一个队列,将递归调用改成循环的方式:
def inner_sort(self, arr, l, r):
        if l >= r:
            return arr
        tasks = [(l, r)]
        while tasks:
            s, e = tasks.pop(0)
            if s >= e:
                continue
            mid = self.partition(arr, s, e)
            tasks.append((s, mid - 1))
            tasks.append((mid + 1, e))
        return arr
运行通过。

发表于 2022-07-30 10:30:10 回复(0)
实现了C++版本的堆排序、归并排序和快速排序
class HeapSort {
public:
    void operator() (vector<int> &nums) {
        for (int i = nums.size() / 2 - 1; i >= 0; --i) {
            adjustHeap(nums, i, nums.size());
        }
        
        for (int j = nums.size() - 1; j >= 0; --j) {
            swap(nums[0], nums[j]);
            adjustHeap(nums, 0, j);
        }
    }
    
    void adjustHeap(vector<int> &nums, int i, int len) {
        int k = 2 * i + 1;
        while (k < len) {
            if (k + 1 < len && nums[k + 1] > nums[k]) {
                ++k;
            }
            
            if (nums[k] > nums[i]) {
                swap(nums[k], nums[i]);
                i = k;
                k = 2 * i + 1;
            } else {
                break;
            }
        }
    }
};


class MergeSort {
public:
    void operator()(vector<int> &nums) {
        mergeSort(nums, 0, nums.size() - 1);
    }
    
    void mergeSort(vector<int> &nums, int left, int right) {
        if (left >= right) return;
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
    
    void merge(vector<int> &nums, int left, int mid, int right) {
        vector<int> aux(right - left + 1, 0);
        int k = 0, i = left, j = mid + 1;
        while (i <= mid && j <= right) {
            if (nums[i] < nums[j]) {
                aux[k++] = nums[i++];
            } else {
                aux[k++] = nums[j++];
            }
        }
        while (i <= mid) {
            aux[k++] = nums[i++];
        }
        while (j <= right) {
            aux[k++] = nums[j++];
        }
        copy(aux.begin(), aux.end(), nums.begin() + left);
    }
};


class QuickSort {
public:
    void operator()(vector<int> &nums) {
        quickSort(nums, 0, nums.size() - 1);
    }
    
    void quickSort(vector<int> &nums, int left, int right) {
        if (left >= right) return;
        int mid = partition(nums, left, right);
        quickSort(nums, left, mid);
        quickSort(nums, mid + 1, right);
    }
    
    int partition(vector<int> &nums, int left, int right) {
        int pivot = nums[left];
        while (left < right) {
            while (left < right && pivot <= nums[right]) --right;
            nums[left] = nums[right];
            while (left < right && nums[left] <= pivot) ++left;
            nums[right] = nums[left];
        }
        nums[left] = pivot;
        return left;
    }
    
};

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    vector<int> MySort(vector<int>& arr) {
        // write code here
        // HeapSort()(arr);
        // MergeSort()(arr);
        QuickSort()(arr);
        return arr;
    }
};


发表于 2022-07-20 14:56:05 回复(0)
冒泡排序:
由于每一轮小循环中会把一个排好的数“冒泡”或者说是“浮”到数组的“顶”上,因此每进行一轮小循环,下一轮需要比较的次数就少一。内层小循环的进行方向应当和泡的堆叠方向是相反的,因为内层小循环进行的方向就是泡的上浮方向,小循环从左往右进行,就是把泡从左边浮到右边。
class Solution {
    
public:
    vector<int> MySort(vector<int>& arr) {
		if (arr.size() <= 1) {
			return arr;
		}
        vector<int>::iterator i = arr.begin();
        vector<int>::iterator j = arr.begin();
        //第一种写法,泡从数组的最左侧开始堆积,向右延伸,而小循环因此就要从数组的右侧向左侧循环。
        //此时每一轮会找到一个最小的数,放在左侧。
        for (i=arr.begin();i<arr.end()-1;i++)
        {
            for (j = arr.end() - 1; j >i; j--)
            {
                if (*j < *(j-1) )
                {
                    swap<int>(*j, *(j - 1));
                }
            }
        }
        //第二种写法,泡从数组的最右侧开始堆积,向左延伸,而小循环因此就要从数组的左侧向右侧循环。
        //此时每一轮会找到一个最大的数,放在右侧。
        for (i = arr.end()-1; i > arr.begin(); i--)
        {
            for (j = arr.begin(); j < i; j++)
            {
                if (*j < *(j+1) )
                {
                    swap<int>(*j, *(j + 1));
                }
            }
        }
        return arr;
    }
};
选择排序
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    vector<int> MySort(vector<int>& arr) {
        // write code here
        if(arr.size()<=1)
        {
            return arr;
        }
        for(auto i=arr.begin();i<arr.end()-1;i++)
        {
            auto minIt=i;
            for(auto j=i;j<=arr.end()-1;j++)
            {
                if(*minIt>*j){
                    minIt=j;
                }
            }
            swap<int>(*i,*minIt);
        }
        return arr;
    }
    
};
插入排序
    vector<int> MySort(vector<int>& arr) {
        // write code here
        if (arr.size() <= 1)
        {
            return arr;
        }
        //i的左边全都是有序序列
        for (auto i = arr.begin() + 1; i <= arr.end() - 1; i++)
        {
            int currentNumber = *i;
            auto j = i;
            for (; j > arr.begin(); j--)
            {
                if (currentNumber < *(j - 1))
                {
                    *j = *(j - 1);
                }
                else 
                {
                    break;
                }
            }
            *j = currentNumber;
            //*j=*i;
        }
        return arr;
    }
希尔排序:
外层循环控制步长逐步减半,内层循环就是把步长从1改为gap的插入排序。在内层循环插入排序时也不需要一个组一个组来,直接遍历就行,因为我们控制的加减gap是可以直接找到这个元素所在组的其他元素的。
因此希尔排序对多个局部小组的排序可以看为:“对每个小组排序都是离散的进行的,就像操作系统中的时间片调度一样,让每个进程都运行一个时间片,然后暂停,换下一个进程运行”。——每个小组中都只新排好了一个元素(或者说是新插好了一个),然后就换到下一个小组去了。
    vector<int> MySort(vector<int>& arr) {
        // write code here
        if (arr.size() <= 1)
        {
            return arr;
        }
        //gap为多少,便是划分为了多少个局部排序小组。
        //第一层循环,让gap不断减半的最外层循环。
        for(int gap=arr.size()/2;gap>=1;gap/=2){
                //内层循环,即插入排序。
                //从第一个元素开始直接向上遍历整个数组,遇到每个元素时能自动
                //匹配它所在的局部排序小组。
                for(int point=gap;point<arr.size();point++)
                {
                    int keyCard=arr[point];
                    int j=point-gap;
                    while(keyCard<arr[j])
                    {
                        arr[j+gap]=arr[j];
                        j-=gap;
                        if(j<0)
                            break;
                    }
                    arr[j+gap]=keyCard;
                }
        }
        return arr;
    }
归并排序
每一次的归并操作都比较类似,因此可以专门写一个函数来进行处理。在顶层的归并操作中进行递归调用,排序左半边,排序右半边,最后归并左右半边。这里使用的是自顶向下的分解式的二路归并,一路下去计算front mid end,分解成了大小只有1的数组时再一层层向上递归归并回去。
    vector<int> Merge(vector<int>& arr, int front, int mid, int end)
    {
        vector<int>leftarr(arr.begin() + front, arr.begin() + mid + 1);
        vector<int>rightarr(arr.begin() + mid + 1, arr.begin() + end + 1);
        leftarr.insert(leftarr.end(), numeric_limits<int>::max());
        rightarr.insert(rightarr.end(), numeric_limits<int>::max());
        int pointLeft =0, pointRight = 0;
        for (int i = front; i <= end; i++)
        {
            if (leftarr[pointLeft] < rightarr[pointRight])
            {
                *(arr.begin()  + i) = leftarr[pointLeft];
                pointLeft++;
            }
            else
            {
                *(arr.begin()  + i) = rightarr[pointRight];
                pointRight++;
            }
        }
        leftarr.clear();
        rightarr.clear();
        return arr;
    }

    vector<int> MergeSort(vector<int>& arr, int front, int end)
    {
        if (front >= end)
            return arr;
        int mid = (front + end) / 2;
        MergeSort(arr, front, mid);
        MergeSort(arr, mid + 1, end);
        Merge(arr, front, mid, end);
        return arr;
    }
    
    vector<int> MySort(vector<int>& arr) {
        // write code here
        if (arr.size() <= 1)
        {
            return arr;
        }
        MergeSort(arr, 0,arr.size()-1);
        return arr;
    }
快速排序:详见代码注释。
 //对数组重新排序,使左侧的数小于基数,右侧的数大于基数。
    int quick(vector<int>& arr,int low,int high){
        int pivot=low;
        int pivotNumber=arr[pivot];
        //如果使用swap来交换的话,赋值操作的次数为3n次
        //而使用这种方式来进行交换,赋值操作的次数仅为n+1次。
        while(low<high){
            while(low<high && arr[high]>pivotNumber){
                high--;
            }
            arr[low]=arr[high];
            while(low<high && arr[low]<pivotNumber){
                low++;
            }
            arr[high]=arr[low];
        }
        arr[low]=pivotNumber;
        return low;
    }
    
    vector<int> QuickSort(vector<int>& arr,int begin,int end)
    {
        //边界条件为新的子数组长度要大于1.
        if(begin>=end || begin>=arr.size() || end>=arr.size())
            return arr;
        //取基数进行排序。
        int pivot=quick(arr,begin,end);
        //对排了一次序后的数组,取基数左右两侧再递归地进行排序。
        QuickSort(arr,begin,pivot);
        QuickSort(arr,pivot+1,end);
        return arr;
    }
    
    vector<int> MySort(vector<int>& arr) {
        // write code here
        int length=arr.size();
        QuickSort(arr,0,arr.size()-1);
        return arr;
    }
堆排序:
 
    //版本1.传统写法。
    vector<int> AdjustHeap(vector<int>& arr,int begin,int end) {
        //让两个子节点与父节点比较,如果子节点更大就让它和父节点交换,否则不动。
        //因为堆是完全二叉树,所以若父节点的序号是n,那么子节点的序号便是2n+1
        int dad=begin;
        int child=begin*2+1;
        while(child<=end)
        {
            //如果存在右孩子
            if (child+1<=end)
            {
                //如果两个孩子中右孩子更大
                if(arr[child]<arr[child+1])
                {
                    child++;
                }
            }
            //如果两个孩子中有个孩子比父亲更大,则交换。
            if(arr[child]>arr[dad])
            {
                swap<int>(arr[child],arr[dad]);

                //继续比较孙辈。
                dad=child;
                child=child*2+1;
            }else
            {    //说明此处节点往下的节点都满足了大根堆的定义,无需继续向下了。
                return arr;
            }
            
        }
        return arr;
    }
    
    vector<int> HeapSort(vector<int>& arr) {
        int arrlength=arr.size();
        if(arrlength<=1)
            return arr;
        //初始化,从最小的一排父节点开始。最后一个父节点(非叶节点)在数组中的
        //序号是length/2 - 1,对于非满二叉树来说,次层的叶节点不用管。
        for(int i=arrlength/2-1;i>=0;i--)
        {
            AdjustHeap(arr,i,arrlength-1);
        }
        //完成初始化后,交换堆中的第一个与最后一个元素,并剔除最后一个元素
        //然后重新调整整个堆,使其重新符合堆的定义。
        for(int i=arrlength-1;i>0;i--)
        {
            swap<int>(arr[0],arr[i]);
            AdjustHeap(arr,0,i-1);
        }
        return arr;
        
    }
    //从题解中看的版本2,利用了优先队列。
    void heapSort(vector<int> &arr) {
        priority_queue<int,vector<int>,greater<int>> q; //小顶堆
 
        for (int i = 0; i < arr.size(); i++) {
            q.push(arr[i]);
        }
        for (int i = 0; i < arr.size(); i++) {
            arr[i] = q.top();
            q.pop();
        }
    }
    
    vector<int> MySort(vector<int>& arr) {
        // write code here
        HeapSort(arr);
        return arr;
    }
计数排序:(内存超过限制,无法排浮点数)
vector<int> CounterSort(vector<int>& arr)
    {
       if(arr.size()<=1)
       {
           return arr;
       }
       int max=arr[0];
       int min=arr[0];
        //找出最大最小值。
       for(int i=0;i<arr.size();i++)
       {
           if(arr[i]>max)
               max=arr[i];
           if(arr[i]<min)
               min=arr[i];
       }
        //对计数器初始化,统计数组中每个数各有多少个
       int counterSize=max-min+1;
       vector<int>counter(counterSize);
       int index=0;
       for(int i=0;i<arr.size();i++)
       {
           //比如最小值是2,现在的值为3,那么就该放到第2个计数器中去,index为1
            index=arr[i]-min;
            counter[index]++;
       }
       //将计数器中的数字弹出来。
        index=0;
        for(int i=0;i<arr.size();i++)
        {
            while(counter[index]==0)
            {
                index++;
            }
            arr[i]=index+min;
            counter[index]--;
            
        }
        return arr;
    }
桶排序:感觉好像没啥人写桶排序啊……翻了几页都翻不到一份。我贡献一份C++的桶排序好了。
    //抄来的堆排序,用于桶内排序。
    void heapSort(vector<int> &arr) {
        priority_queue<int,vector<int>,greater<int> > q; //小顶堆
  
        for (int i = 0; i < arr.size(); i++) {
            q.push(arr[i]);
        }
        for (int i = 0; i < arr.size(); i++) {
            arr[i] = q.top();
            q.pop();
        }
    }
    vector<int> BucketSort(vector<int>& arr)
    {
       int max=*max_element(arr.begin(),arr.end());
        int min=*min_element(arr.begin(),arr.end());
        //找出绝对值最大值。
        
       int power=(int)log2(max);
        //建桶,注意power要加1。这里坑了我好久。
        //因为我们是希望桶的个数是从幂=0~n的,即一共要n+1个桶。
       vector<vector<int> >Buckets(power+1);
        /*for(int i=0;i<=power;i++)
        {
            Buckets[i]=new (vector<int>);
        }
        */
       for(int i=0;i<arr.size();i++)
       {
           //确定每个数的大小应该归属于哪个桶,并塞进去。
           int currentPower=(int)log2(arr[i]);
           Buckets[currentPower].push_back(arr[i]);
       }
       //用于把桶中的东西倒回去的指针,指示现在倒到哪了。
       int index=0;
       for(auto bucket:Buckets)
       {
           heapSort(bucket);
           for(auto j:bucket)
           {
               arr[index++]=j;
           }
       }
        return arr;
    }



编辑于 2022-07-28 23:33:19 回复(0)
优化过的冒泡排序一样可以通过。
冒泡算法优化思路:
1. 外循环优化:如果某次比较过程中,发现没有任何元素移动,则不再进行接下来的比较。具体的做法是在每趟比较时,引入一个boolean型变量isSwap,来判断下次比较还有没有必要进行。举个栗子,如果对一个有序数组进行冒泡排序,那么只需要排第一趟,剩余的趟数不再进行。
2. 内循环优化外循环优化比较容易理解,但同时也存在着缺点:某趟比较只要开始,哪怕数组元素已经有序,也要把该趟的所有次比较完。也就是说,第一种优化方式,只能在“趟”的级别上优化。第二种优化方式,也就是要实现在“次”的级别进行优化,其思路是“记下最后一次交换的位置,后边没有交换,必然是有序的,然后下一次排序从第一个比较到上次记录的位置结束即可”。
下面的冒泡算法是结合两种优化方式进行的,成功通过。
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        // 冒泡排序
        return bubbleSort(arr);
    }
    
    //优化过的冒泡排序
    private int[] bubbleSort(int[] array){
      
        int position = array.length - 1;
        /*外循环为排序趟数,array.length个数进行array.length-1趟 */
        for(int i = 0;i<array.length-1;i++){
        	boolean isSwap = false;
        	/*用来记录最后一次交换的位置*/
        	int newPosition = 0;
        	/*内循环为每趟比较的次数,第i趟比较array.length-i次 */
            for(int j = 0;j<position;j++){
            	 /*相邻元素比较,若满足条件则交换(升序为左大于右,降序反之) */
                if(array[j]>array[j+1]){
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                    isSwap = true;
                    /*记录最后一次交换的位置*/
                    newPosition = j;
                }
                /*查看每趟比较后的数组元素*/
//                 System.out.println("第 "+(i+1)+" 趟,第 "+(j+1)+" 次比较后的结果:");
//                 for(int k = 0;k<array.length;k++){
//                     System.out.print(array[k]+" ");
//                 }
//                 System.out.println();
            }
            /*如果没有交换过元素,则已经有序,不再进行接下来的比较*/
            if(!isSwap){
            	break;
            }
            /*下趟比较所需要比较到的位置*/
            position = newPosition;
        }
        
        return array;

    }
    
}





发表于 2022-03-20 21:44:52 回复(0)
class Solution:
    def MySort(self , arr ):
        # write code here
        arr.sort()
        return arr
        #或:
#         return sorted(arr)

发表于 2022-02-22 21:37:20 回复(0)
归并排序
    public int[] MySort (int[] arr) {
        // write code here
        trueMergeSort(arr,new int[arr.length],0,arr.length-1);
        return arr;
    }
    
    public static void trueMergeSort(int[] arr,int[] tempArr,int left,int right){
        if(left >= right){
            return;
        }
        int mid = (left+right)/2;
        trueMergeSort(arr,tempArr,left,mid);
        trueMergeSort(arr,tempArr,mid+1,right);
        partitionMerge(arr,tempArr,left,right);
    }
    
    public static void partitionMerge(int[] arr,int[] tempArr,int left,int right){
        int mid = (left + right)>>>1;
        int lPointer = left,rPointer = mid+1,tempIndex = left;
        while(lPointer<=mid && rPointer<=right){
            tempArr[tempIndex++] = arr[lPointer]>arr[rPointer]?
                arr[rPointer++]:arr[lPointer++];
        }
        while(lPointer<=mid){
            tempArr[tempIndex++]=arr[lPointer++];
        }
        while(rPointer<=right){
            tempArr[tempIndex++]=arr[rPointer++];
        }
        for(int i=left;i<=right;i++){
            arr[i] = tempArr[i];
        }
    }


发表于 2021-12-04 11:24:58 回复(0)
class myCompare
{
    public:
     bool operator()(int v1,int v2)
    {
        return v1 < v2;
    }
};
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
   
    vector<int> MySort(vector<int>& arr) {
        sort(arr.begin(),arr.end(),myCompare());
        return arr;
        // write code here
    }
};
仿函数
发表于 2021-08-30 00:42:30 回复(0)
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        sort(arr);
        return arr;
    }
    public static void sort(int []arr){
        //1.构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
            //从第一个非叶子结点从下至上,从右至左调整结构
            adjustHeap(arr,i,arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for(int j=arr.length-1;j>0;j--){
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);//重新对堆进行调整
        }

    }

    /**
     * 调整大顶堆(仅是调整过程,建立在大顶堆已构建的基础上)
     * @param arr
     * @param i
     * @param length
     */
    public static void adjustHeap(int []arr,int i,int length){
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始,也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点,k指向右子结点
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

    /**
     * 交换元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
    
}

发表于 2021-05-26 23:15:35 回复(0)
C++ 快速排序:
class Solution {
public:
    vector<int> MySort(vector<int>& arr) {
        if(arr.size() == 0)    return {};
        
        quicksort(arr, 0, arr.size()-1);
        
        return arr;
    }
    
    int partition(vector<int>& arr, int left, int right) {
        // 取数组中最右边的值为主元
        int count = left;        // 记录小于主元的个数
        while(left < right) {
            if(arr[left] < arr[right]) {
                swap(arr[left], arr[count]);
                ++count;
            }
            ++left;
        } 
        swap(arr[count], arr[right]);
        return count;
    }
    
    void quicksort(vector<int>& arr, int left, int right) {
        if(left > right)        // 递归结束条件
            return ;
        int privotIndex = partition(arr, left, right);
        quicksort(arr, left, privotIndex-1);
        quicksort(arr, privotIndex+1, right);
    }
};


编辑于 2021-06-03 16:35:53 回复(0)
  public int[] MySort (int[] arr) {
        // write code here
        Arrays.sort(arr);
        return arr;
    }
你强任你强
发表于 2021-12-09 16:34:12 回复(0)
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        if(arr.length==0) return arr;
        PriorityQueue<Integer> pq=new PriorityQueue<>();
        int[] ans=new int[arr.length];
        for(int i=0;i<arr.length;i++){
            pq.offer(arr[i]);
        }
        for(int i=0;i<arr.length;i++){
            ans[i]=pq.poll();
        }
      //  while(!pq.isEmpty()) 
        return ans;
    }
}

发表于 2021-10-11 16:10:51 回复(5)
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        sort(arr, 0, arr.length - 1);
        return arr;
    }
    
    public void sort(int[] a, int low, int high) {
        // 递归终止条件
        if(low >= high) {
            return;
        }
        int i = low;
        int j = high;
        // 基准位
        int temp = a[low];
        while(i < j) {
            // 找出从右到左第一个小于基准位的数下标
            while(i < j && temp <= a[j]) {
                j--;
            }
            // 找出从左到右第一个大于基准位的数下标
            while(i < j && temp >= a[i]) {
                i++;
            }
            if(i < j) {
                swap(a, i, j);
            }
        }
        // 此时 i==j
        swap(a, low, i);
        sort(a, low, i-1);
        sort(a, i+1, high);
    }
    
    public void swap(int[] a, int i, int j) {
        int c = a[i];
        a[i] = a[j];
        a[j] = c;
    }
}

发表于 2021-04-06 17:36:50 回复(1)
//简单明了的java代码
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        quickSort(arr,0,arr.length-1);
        return arr;
    }
    
    public void quickSort(int[] arr, int left, int right) {
        int left_copy = left;
        int right_copy = right;
        int ken = arr[left];//每次取数组的最左作为基准数
        int flag = 0; // 填坑:0表示坑在左边,1表示坑在右边
        while (left < right) {
            if (flag == 0) {
                if (ken > arr[right]) {
                    arr[left] = arr[right];
                    left++;
                    flag = 1;//坑换到右边
                } else if (ken <= arr[right]) {
                    right --;
                }
            } else if (flag == 1) {
                if (ken < arr[left]) {
                    arr[right] = arr[left];
                    right--;
                    flag = 0;//坑换到左边
                } else if (ken >= arr[left]) {
                    left ++;
                }
            } 
        }
        arr[left] = ken;//把基准数填在最后左右见面的位置
        if (left_copy < left-1)
            quickSort(arr, left_copy, left-1);
        if (left + 1 < right_copy)
            quickSort(arr, left+1, right_copy);
    }
}


发表于 2021-03-16 10:26:42 回复(0)
/**
 * 使用sort函数
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 * 将给定数组排序
 * @param arr int整型一维数组 待排序的数组
 * @return int整型一维数组
 */
function MySort( arr ) {
    return arr.sort((a,b)=>a-b)
}
module.exports = {
    MySort : MySort
};


发表于 2021-09-10 00:19:29 回复(0)
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    vector<int> MySort(vector<int>& arr) {
        // write code here
        mySort1(arr);
        return arr;
    }
    // 1、快速排序(通过)
    // 时间复杂度O(logn)。空间复杂度是O(n)。
    // 主要是要找出标杆值(中间值),默认最后一个值为标杆值,然后比它小的放左边,比他大的放右边,然后交换最后一位。就得到标杆值在中间的下标。
// 树,从上往下排序
    // 不稳定算法
    void mySort1(vector<int>& arr) {
        quicksort(arr, 0, arr.size()-1);
    }  
    void quicksort(vector<int> &arr, int left, int right) {
        if (left > right) return;

        int pivotIndex = partition(arr, left, right); // 标杆值所在的位置
        quicksort(arr, left, pivotIndex-1); // 左半边
        quicksort(arr, pivotIndex+1, right); // 右半边
    }
    // 这里只需要把数据归类就行,不需要比较大小;每次比标杆值小的放左边,比标杆值大的放右边。
    int partition(vector<int> &arr, int left, int right) {
        // 最后一个值当做标杆(自己随意定)
        int mark = arr[right];
        // 记录小于标杆值的个数
        int counter = left;      
        for (int i = left; i < right; i++) {
            if (arr[i] < mark) { // 当前值和标杆值比较,决定是放在左边还是右边
               swap(arr[i], arr[counter++]);
           }
        }
        swap(arr[counter], arr[right]);   // 最后把标杆值移到中间位置,然后返回下标。
        return counter;
    }


    // 2、归并排序(通过)
    // 时间复杂度O(logn)。空间复杂度是O(n)。
    // 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
    // 树,从下往上排序
    // 是稳定的算法
    void mySort2(vector<int>& arr) {
        mergeSort(arr, 0, arr.size()-1);
    }  

    void mergeSort(vector<int> &arr, int left, int right) {
        if (left >= right) return;

        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid); // 递归 左半边
        mergeSort(arr, mid+1, right); // 递归 右半边

        merge(arr, left, mid, right); // 合并两个有序的数组(参考合并两个有序的链表)
    }

    // 合并两个有序数组
    void merge(vector<int> &arr, int left, int mid, int right) {
        vector<int> tmp(right-left+1); // 开辟新的数组
        int i = left, j = mid+1, k = 0; // i左边数组的起始位置,j右边数组的起始位置,k已经放入新数组的个数

        while (i <= mid && j <= right) {  // 比较左右数组,数值小的放入新数组中
            tmp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= mid) tmp[k++] = arr[i++];  // 如果左半边数组没有排序完,加入新数组
        while (j <= right) tmp[k++] = arr[j++]; // 如果右半边数组没有排序完,加入新数组

        for (i = left, k = 0; i <= right;) arr[i++] = tmp[k++]; // 新数组数据放回到原来的数组中
    }
    // 3、堆排序(通过)
    // 时间复杂度O(logn)。空间复杂度是O(n)。
    // 不稳定算法
    void heapSort(vector<int> &arr) {
        priority_queue<int,vector<int>,greater<int>> q; //小顶堆

        for (int i = 0; i < arr.size(); i++) {
            q.push(arr[i]);
        }
        for (int i = 0; i < arr.size(); i++) {
            arr[i] = q.top();
            q.pop();
        }
    }

    // 4、冒泡排序(超时)
    // 时间复杂度O(n2),空间复杂度O(1)
    // 从后往前排
    // 两两比较交换,最大的放在后面,稳定排序
    void bubbleSort(vector<int>& arr) {

        for (int i = 0; i < arr.size(); i++) {
            for (int j = 0; j < arr.size()-i-1; j++) {
                if (arr[j]>arr[j+1]) {
                    swap(arr[j], arr[j+1]);
                }
            }
        }
    }

    // 5、选择排序(超时)
    // 时间复杂度O(n2),空间复杂度O(1)
    // 从前往后排
    // 遍历数组,找出最小值,最小的放在前面,不稳定排序
    void selectionSort(vector<int>& arr) {
        int minIndex = 0;
        for (int i = 0; i < arr.size(); i++) {
            minIndex = i;
            for (int j = i+1; j < arr.size(); j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(arr[i], arr[minIndex]);
        }
    }

    // 6、插入排序(超时)
    // 时间复杂度O(n2),空间复杂度O(1)
    // 从前往后排
    // 遍历数组,找出一个值,往排好的数组里面插入合适的位置。稳定排序
    void insetionSort(vector<int>& arr) {
        int preIndex = 0;
        int currentVal = 0;

        for (int i = 1; i < arr.size(); i++) {
            preIndex = i - 1;
            currentVal = arr[i];

            while (preIndex >= 0 && arr[preIndex] > currentVal) {
                arr[preIndex+1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex+1] = currentVal;
        }
    }


};

编辑于 2021-09-27 19:44:13 回复(3)
python实现:
class Solution:
    def MySort(self , arr ):
        # write code here
#         return self.bubble_sort(arr)
#         return self.select_sort(arr)
#         return self.insert_sort(arr)
        return self.quick_sort(arr)
#         return self.merge_sort(arr)
         
    def bubble_sort(self, arr):
        # 冒泡排序 不通过
        for i in range(len(arr) - 1):
            for j in range(len(arr) - i - 1):
                if arr[j] > arr[j+1]:
                    arr[j], arr[j+1] = arr[j+1], arr[j]
        return arr
       
    def select_sort(self, arr):
        # 选择排序 不通过
        for i in range(len(arr)):
            min_index = i
            for j in range(i+1, len(arr)):
                if arr[j] < arr[min_index]:
                    min_index = j
            arr[min_index], arr[i] = arr[i], arr[min_index]
        return arr
    
    def insert_sort(self, li):
        # 插入排序 不通过
        for i in range(1, len(li)):
            tmp = li[i]                     # tmp要插入的之
            j = i - 1
            while j >= 0 and li[j] > tmp:   # 前面的值比tmp大
                li[j+1] = li[j]             # 前面的值向后移一位
                j = j - 1                   # 继续向前对比
            li[j+1] = tmp                   # 直到while不满足条件, 也就是前面的值比tmp小, 插入到比tmp小的值后
        return li
    
    def quick_sort(self, li):
        # 快速排序 通过
        if len(li) < 2:
            return li
        else:
            tmp = li[0]
            less = [i for i in li[1:] if i <= tmp]
            more = [i for i in li[1:] if i > tmp]
            return self.quick_sort(less) + [tmp] + self.quick_sort(more)
        
    def merge_sort(self, li):
        # 归并排序 可能通过 可能不通过
        if len(li) < 2:
            return li
        else:
            num = len(li) // 2
            left = self.merge_sort(li[:num])
            right = self.merge_sort(li[num:])
            return self.merge(left, right)
        
    def merge(self, left, right):
        l,r = 0,0
        result = []
        while l < len(left) and r < len(right):
            if left[l] < right[r]:
                result.append(left[l])
                l += 1
            else:
                result.append(right[r])
                r += 1
        result += left[l:]
        result += right[r:]
        return result


编辑于 2021-03-03 10:59:35 回复(5)
/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 * 将给定数组排序
 * @param arr int整型一维数组 待排序的数组
 * @param arrLen int arr数组长度
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
#include<stdio.h>
void Swap(int* p1, int* p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

// 冒泡排序会超时
void BuubleSort(int* arr, int arrlen)
{
    for (int i = 0; i < arrlen; i++)
    {
        for (int j = 1; j < arrlen; j++)
        {
            if (arr[j - 1] > arr[j])
            {
                Swap(&arr[j - 1], &arr[j]);
            }
        }
    }
}

// 选择排序超时
void SelectSort(int* arr, int arrlen)
{
    int begin = 0;
    int end = arrlen - 1;

    while (begin <= end)
    {
        int maxi = begin;
        int mini = begin;
        for (int i = begin; i <= end; i++)
        {
            if (arr[i] > arr[maxi])
            {
                maxi = i;
            }

            if (arr[i] < arr[mini])
            {
                mini = i;
            }
        }

        Swap(&arr[begin], &arr[mini]);
        if (maxi == begin)
        {
            maxi = mini;
        }
        Swap(&arr[maxi], &arr[end]);

        end--;
        begin++;
    }
}
//插入排序 (可以通过)
void InsertSort(int* arr, int arrlen)
{
    for (int i = 0; i < arrlen - 1; i++)
    {
        int end = i;
        int key = arr[end + 1];
        /*while (end >= 0)
        {
            while (arr[end] > key)
            {
                arr[end + 1] = arr[end];
                end--;
            }
            arr[end + 1] = key;
            break;
        }
        */
        while (end >= 0)
        {
            if (arr[end] > key)
            {
                arr[end + 1] = arr[end];
                end--;
            }
            else
            {
                break;
            }
        }
        arr[end + 1] = key;
    }
}

//希尔排序通过
void ShellSort(int* arr, int arrLen)
{
    int gap = arrLen;
    while (gap > 1)
    {
        gap = gap / 2;

        for (int i = 0; i < arrLen - gap; i++)
        {
            int end = i;
            int key = arr[end + gap];

            while (end >= 0)
            {
                if (arr[end] > key)
                {
                    arr[end + gap] = arr[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            arr[end + gap] = key;
        }

    }
}

//挖坑法的快速排序
int PartSort(int* arr, int left, int right)
{
    int pvoit = left;
    int key = arr[pvoit];
    while (left < right)
    {
        while (left < right && arr[right] >= key)
        {
            right--;
        }
        arr[pvoit] = arr[right];
        pvoit = right;

        while (left < right && arr[left] <= key)
        {
            left++;
        }
        arr[pvoit] = arr[left];
        pvoit = left;
    }
    arr[pvoit] = key;
    return  pvoit;
}


void QuickSort(int* arr, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int pvoit = PartSort(arr, left, right);
    QuickSort(arr, left, pvoit - 1);
    QuickSort(arr, pvoit + 1, right);


}

//归并排序
void _MergeSort(int* arr, int left, int right, int* tmp)
{
    if (left >= right)
    {
        return;
    }
    int mid = (left + right) >> 1;
    _MergeSort(arr, left, mid, tmp);
    _MergeSort(arr, mid + 1, right, tmp);

    int begin1 = left;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = right;
    int index = left;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (arr[begin1] < arr[begin2])
        {
            tmp[index++] = arr[begin1++];
        }
        else
        {
            tmp[index++] = arr[begin2++];
        }
    }

    while (begin1 <= end1)
    {
        tmp[index++] = arr[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[index++] = arr[begin2++];
    }

    for (int i = left; i <= right; i++)
    {
        arr[i] = tmp[i];
    }

}
void MergeSort(int* arr, int left, int right)
{
    int* tmp = (int*)malloc(sizeof(int) * (right - left + 1));
    _MergeSort(arr, left, right, tmp);
    free(tmp);
    tmp = NULL;

}

void AdjustDwon(int* arr, int arrLen, int root)
{
    int parent = root;
    int child = parent * 2 + 1;//默认是左孩子

    while (child < arrLen)
    {
        if (child + 1 < arrLen && arr[child + 1] > arr[child])
        {
            child += 1;
        }

        if (arr[child] > arr[parent])
        {
            Swap(&arr[child], &arr[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
void HeapSort(int* arr, int arrLen)
{
    //建堆
    for (int i = (arrLen - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDwon(arr, arrLen, i);
    }

    int end = arrLen - 1;
    while (end > 0)
    {
        Swap(&arr[0], &arr[end]);
        AdjustDwon(arr, end, 0);
        end--;
    }
}
int* MySort(int* arr, int arrLen, int* returnSize)
{
    // write code here
    //BuubleSort(arr, arrLen);
    //SelectSort(arr, arrLen);
    //InsertSort(arr, arrLen);
    //ShellSort(arr, arrLen);
    //MergeSort(arr, 0, arrLen - 1);
    //HeapSort(arr, arrLen);
    QuickSort(arr, 0,arrLen - 1);
    *returnSize = arrLen;
    return arr;
}

七大排序:冒泡和选择超时,插入排序。希尔排序。快速排序。归并排序。堆排序
编辑于 2021-06-27 16:20:18 回复(4)
//此代码适用于像我这样的萌新小白们,直接使用数组自带的sort方法排序,代码简洁可读性高,
//缺点就是运行时间长,在大佬眼里的破代码哈哈哈。
import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        if(arr==null){
            return null;
        }
        if(arr!=null){
            Arrays.sort(arr);
        }
        return arr;
    }
}


发表于 2021-09-18 10:10:01 回复(2)
我能第一时间想到的最方便最简单的方法就是这个了,可能我比较菜***。Arrays.sort(arr)
发表于 2021-07-19 16:05:25 回复(2)
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        // 快速排序,时间复杂度O(N*logN),空间复杂度O(logN),不稳定
        quickSort(arr, 0, arr.length - 1);
        // 归并排序,时间复杂度O(N*logN),空间复杂度O(N),稳定
        // mergeSort(arr);
        // 堆排序(大根堆),时间复杂度O(N*logN),空间复杂度O(N),不稳定
        // heapSort(arr);
        // 希尔排序,时间复杂度O(N*logN),空间复杂度O(1),不稳定
        // shellSort(arr);
        // 基数排序,时间复杂度O(C*N),C为2*(数值长度+1),空间复杂度O(K+N),K为数值长度,稳定
        // baseSort(arr);
        return arr;
    }
    
    private void quickSort (int[] arr, int left, int right) {
        if (left < right) {
            int idx = partition(arr, left, right);
            quickSort(arr, left, idx - 1);
            quickSort(arr, idx + 1, right);
        }
    }
    
    private int partition (int[] arr, int left, int right) {
        int mark = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= mark) {
                right--;
            }
            if (left < right) {
                arr[left++] = arr[right];
            }
            while (left < right && arr[left] <= mark) {
                left++;
            }
            if (left < right) {
                arr[right--] = arr[left];
            }
        }
        arr[left] = mark;
        return left;
    }
    
    
    private void mergeSort (int[] arr) {
        int[] tmp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, tmp);
    }
    
    private void mergeSort (int[] arr, int left, int right, int[] tmp) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid, tmp);
            mergeSort(arr, mid + 1, right, tmp);
            merge(arr, left, right, tmp);
        }
    }
    
    private void merge(int[] arr, int left, int right, int[] tmp) {
        int mid = left + (right - left) / 2, i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= mid) {
            tmp[k++] = arr[i++];
        }
        while (j <= right) {
            tmp[k++] = arr[j++];
        }
        k = 0;
        while (left <= right) {
            arr[left++] = tmp[k++];
        }
    }
    
    private void heapSort (int[] arr) {
        int len = arr.length, buildMaxHeapLoopLimit = arr.length / 2;
        for (int i = buildMaxHeapLoopLimit; i >= 0; i--) {
            heapify(arr, i, len);
        }
        for (int i = len - 1; i > 0; i--) {
            swap(arr, i, 0);
            len--;
            heapify(arr, 0, len);
        }
    }
    
    private void heapify (int[] arr, int cur, int len) {
        int left = 2 * cur + 1, right = 2 * cur + 2, maxIdx = cur;
        if (left < len && arr[left] > arr[maxIdx]) {
            maxIdx = left;
        }
        if (right < len && arr[right] > arr[maxIdx]) {
            maxIdx = right;
        }
        if (cur != maxIdx) {
            swap(arr, cur, maxIdx);
            heapify(arr, maxIdx, len);
        }
    }
    
    
    private void shellSort(int[] arr) {
        for (int step = arr.length / 2; step >= 1; step /= 2) {
            for (int i = step, tmp, j; i < arr.length; i++) {
                tmp = arr[i];
                j = i - step;
                while (j >= 0 && arr[j] > tmp) {
                    arr[j + step] = arr[j];
                    j -= step;
                }
                arr[j + step] = tmp;
            }
        }
    }
    
    
    private void baseSort (int[] arr) {
        List<List<Integer>> bucketList = new ArrayList<>();
        // 建立0-9,共10个桶
        int baseCount = 10, numSize = 10;
        for (int i = 0; i < baseCount; i++) {
            bucketList.add(new ArrayList<>());
        }
        for (int i = 0; i < numSize; i++) {
            for (int num : arr) {
                bucketList.get(getBaseNum(num, i)).add(num);
            }
            int j = 0;
            for (List<Integer> bucket : bucketList) {
                for (Integer num : bucket) {
                    arr[j++] = num;
                }
                bucket.clear();
            }
        }
        // 负数的存在,需使用正/负数桶
        List<Integer> posBucket = bucketList.get(0), negBucket = bucketList.get(1);
        for (int num : arr) {
            if (num > 0) {
                posBucket.add(num);
            } else {
                negBucket.add(num);
            }
        }
        int idx = 0;
        for (int i = negBucket.size() - 1; i >= 0; i--) {
            arr[idx++] = negBucket.get(i);
        }
        for (Integer num : posBucket) {
            arr[idx++] = num;
        }
    }
    
    private int getBaseNum (int val, int count) {
        val = Math.abs(val);
        for (int i = 0; i < count; i++) {
            val /= 10;
        }
        return val %= 10;
    }
    
    
    private void swap (int[] arr, int x, int y) {
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }
}

发表于 2021-08-18 15:30:38 回复(0)