题解 | #排序#

选择排序
c++

class Solution {
public:
    //选择排序
    vector<int> MySort(vector<int>& arr) {
        // write code here
        int n = arr.size();
        for(int i = 0 ; i < n ; i++)
        {
            int minn = arr[i];
            int mini = i;
            for(int j = i+1 ; j < n ; j++ )
            {
                if(arr[j] <minn)
                {
                    minn = arr[j];
                    mini = j;
                }
            }
            swap(arr[i],arr[mini]);
        }
        return arr;
    }
};

python
c++

class Solution:
    def MySort(self , arr ):
        n = len(arr);
        for i in range(0,n):
            minn = arr[i];
            mini = i;
            for j in range(i+1,n):
                if arr[j] < minn:
                    minn = arr[j]
                    mini = j
            arr[i],arr[mini] = arr[mini],arr[i]
        return arr

冒泡排序
c++

class Solution {
public:
    //冒泡排序
    vector<int> MySort(vector<int>& arr) {
        int n = arr.size();
        for(int i = 0 ; i < n-1 ; i++ )
        {
            bool flag = false;
            for(int j = 0 ; j < n-1-i ; j++)
            {
                if(arr[j] > arr[j+1])
                {
                    flag = true;
                    swap(arr[j],arr[j+1]);
                }
            }
            if(!flag){break;}
        }
        return arr;
    }
};

python

class Solution:
    def MySort(self , arr ):
        n = len(arr);
        for i in range(0,n-1):
            flag = False;
            for j in range(0,n-1-i):
                if arr[j] > arr[j+1]:
                    flag = True;
                    arr[j],arr[j+1] = arr[j+1],arr[j]
            if flag==False:
                break
        return arr

插入排序
c++

class Solution {
public:
    //插入排序
    vector<int> MySort(vector<int>& arr) {
        int n = arr.size();
        for(int i = 1 ; i < n ; i++)
        {
            int key = arr[i];
            int j = i-1;
            while(j>0&&arr[j]>key)
            {
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = key;
        }
        return arr;
    }
};

python

class Solution:
    def MySort(self , arr ):
        n = len(arr);
        for i in range(1,n):
            key = arr[i]
            j = i-1;
            while j>=0 and arr[j]>key:
                arr[j+1] = arr[j]
                j = j-1
            arr[j+1] = key;
        return arr

希尔排序
c++

class Solution {
public:
    //希尔排序
    vector<int> MySort(vector<int>& arr) {
        int n = arr.size();
        int gap = n /2;
        while(gap >=1)
        {
            for(int i = gap ; i < n ; i++)
            {
                int key = arr[i];
                int j = i-gap;
                while(j>=0 && arr[j]>key)
                {
                    arr[j+gap] = arr[j];
                    j = j-gap;
                }
                arr[j+gap] = key;
            }
            gap = gap/2;
        }

        return arr;
    }
};

python

class Solution:
    def MySort(self , arr ):
        # write code here
        gap = len(arr)//2
        while(gap>=1):
            for i in range(gap, len(arr)):
                j = i-gap
                key = arr[i]
                while j >= 0 and arr[j]>key:
                    arr[j+gap] = arr[j]
                    j -= gap
                arr[j+gap] = key
            gap //= 2
        return arr

快速排序
c++

class Solution {
public:
    //快速排序
    int partition(vector<int>&arr,int l,int r)
    {
        int x = arr[l];
        while( l < r )
        {
            while(l < r && arr[r] >= x) { r--;}
            arr[l] = arr[r];
            while(l < r && arr[l] < x) { l++;}
            arr[r] = arr[l];
        }
        arr[l] = x;
        return l;
    }
    void quicksort(vector<int>&arr,int l,int r)
    {
        if(l<r)
        {
            int mid = partition(arr,l,r);
            quicksort(arr,l,mid-1);
            quicksort(arr,mid+1,r);
        }
    }
    vector<int>MySort(vector<int>&arr){
        int n = arr.size();
        quicksort(arr,0,n-1);
        return arr;
    }
};

归并排序
c++

class Solution {
public:
    //归并排序
    void Merge(vector<int>& arr,int l,int r)
    {
        int mid = (l+r)/2;
        int lenL = mid - l +1;
        int lenR = r- mid ;
        int *L = new int[lenL];
        int *R = new int[lenR];
        for(int i = 0 ; i < lenL ; i++)
        {
            L[i] = arr[l+i];
        }
        for(int i = 0 ; i < lenR ; i++)
        {
            R[i] = arr[mid+1+i];
        }
        int i = 0;
        int j = 0;
        for(int index = l ; index <= r ; index++)
        {
            if(j>=lenR || (i<lenL && L[i] < R[j]))
            {
                arr[index] = L[i];
                i++;
            }
            else{
                arr[index] = R[j];
                j++;
            }
        }
        delete []L;
        delete []R;
    }
    void mergeSort(vector<int>& arr,int l,int r)
    {
        if(l<r)
        {
            int mid = (l+r)/2;//l+(r-l)/2
            mergeSort(arr,l,mid);
            mergeSort(arr,mid+1,r);
            Merge(arr,l,r);
        }
    }
    vector<int> MySort(vector<int>& arr) {
        int n = arr.size();
        mergeSort(arr,0,n-1);
        return arr;
    }
};

堆排序
c++

class Solution {
public:
    int heapSize;
    int Left(int i)
    {
        if(i*2+1 >= heapSize) {return -1;}
        return i*2+1;
    }
    int Right(int i)
    {
        if(i*2+2 >= heapSize) {return -1;}
        return i*2+2;
    }
    void maxHeapify(vector<int>& arr,int i)
    {
        int L = Left(i);
        int R = Right(i);
        int maxi = i;
        if(L != -1 && arr[L]>arr[i]){maxi = L;}
        if(R != -1 && arr[R]>arr[maxi]){maxi = R;}
        if(maxi != i)
        {
            swap(arr[i],arr[maxi]);
            maxHeapify(arr, maxi);
        }
    }
    void Delete(vector<int>& arr)
    {
        swap(arr[heapSize-1],arr[0]);
        heapSize = heapSize-1;
        maxHeapify(arr, 0);
    }
    //堆排序
    vector<int> MySort(vector<int>& arr) {
        int n = arr.size();
        heapSize = n;
        for(int i = (n-1)/2 ;i >= 0 ; i--)
        {
            maxHeapify(arr,i);
        }
        for(int i = 0 ; i < n ; i++)
        {
            Delete(arr);
        }
        //reverse(arr.begin(),arr.end());
       // minHeapify(arr,1);
        return arr;
    }
};