当前位置：首页 > news >正文

排序算法，咕咕咕

news 2025/7/27 9:11:30

1.选择排序

void selectsort(vector<int>& v)
{
for(int i=0;i<v.size()-1;i++)
{int mini=i;for(int j=i+1;j<v.size();j++){if(v[i]>v[j]){mini=j;}}if(mini!=i)swap(v[i],v[mini]);
}
}

2.堆排序

void adjustdown(vector<int>& v,int root,int size)
{
int largest=root;
int left=2*root+1;
int right=2*root+2;
if(left<size&&v[left]>v[largest]) largest=left;
if(right<size&&v[right]>v[largest]) largest=right;
if(largest!=root)
{swap(v[root],v[largest]);adjustdown(v,largest,size);
}}
void heapsort(vector<int>& v)
{
int n=v.size();
for(int i=n/2-1;i>=0;i--)    非叶子结点
{adjustdown(v,i,n);
}
for(int i=n-1;i>0;i--)       大堆只是父结点大于子节点，相邻子节点不一定大于
{
swap(v[i],v[0]);
adjustdown(v,0,n);
}
}

3.插入排序

void insertsort(vector<int>& v)
{int n=v.size();for(int i=1;i<n;i++){int key=v[i];int j=i-1;while(j>=0&&v[j]>key){v[j+1]=v[j];j--;}v[j+1]=key;}
}

4.希尔排序

void shellsort(vector<int>& v)
{int n=v.size();int gap=1;while(gap<n/3){gap=gap*3+1;}for(;gap>0;gap=(gap-1)/3){for(int i=gap;i<n;i++){int key=v[i];int j=i-gap;while(j>=0&&v[j]>key){v[j+gap]=v[j];j-=gap;}v[j+gap]=key;}}
}

5.冒泡排序

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

6.快速排序

//快速排序 hoare法
int findkeyi(vector<int>& arr,int left,int right)
{
int pivot=arr[left];
int i=left-1;
int j=right+1;
while(true)
{do{i++;}while(arr[i]<pivot);do{j++;}while(arr[j]>pivot);if(i>=j) return j;swap(arr[i],arr[j]);
}
}
void quicksort(vector<int>& arr,int left,int right)
{
if(left<right)
{int gugu=findkeyi(arr,left,right);quicksort(arr,left,gugu);quicksort(arr,gugu+1,right);
}
}
//挖坑法
int findkeyi(vector<int>& arr,int left,int right)
{int pivot=arr[left];int hole=left;while(left<right){while(left<right&&arr[right]>=pivot) right--;arr[hole]=arr[right];hole=right;while(left<right&&arr[left]<=pivot) left++;arr[hole]=arr[left];hole=left;}arr[hole]=pivot;return hole;
}
void quicksort(vector<int>& arr,int left,int right)
{if(left<right){int gugu=findkeyi(arr,left,right);quicksort(arr,left,gugu-1);quicksort(arr,gugu+1,right);}
}
//lomuto
int findkeyigugu(vector<int>& arr,int left,int right)
{int pivot=arr[right];int i=left-1;for(int j=left;j<right;j++){if(arr[j]<pivot){i++;swap(arr[i],arr[j]);}}swap(arr[i+1],arr[right]);return i+1;
}
void quicksort(vector<int>& arr,int left,int right)
{if(left<right){int gugu=findkeyi(arr,left,right);quicksort(arr,left,gugu-1);quicksort(arr,gugu+1,right);}
}
//非递归双指针
void quicksort(vector<int>& arr,int left,int right)
{stack<pair<int,int>> st;st.push({left,right});while(!st.empty()){auto [l,r]=st.top();st.pop();if(l>=r) continue;int gugu=findkeyigugu(arr,l,r);st.push({gugu+1,r});st.push({l,gugu-1});}
}

7.归并排序

void merge(vector<int>& arr,int left,int mid,int right)
{int n1=mid-left+1;int n2=right-mid;vector<int> gu(n1),gugu(n2);for(int i=0;i<n1;i++){gu[i]=arr[left+i];}for(int j=0;j<n2;j++){gugu[j]=arr[mid+1+j];}int i=0;int j=0;int k=left;while(i<n1&&j<n2){if(gu[i]<gugu[j]){arr[k]=gu[i];i++;}else{arr[k]=gugu[j];j++;}k++;}while(i<n1){arr[k]=gu[i];i++;k++;}while(j<n2){arr[k]=gugu[j];k++;j++;}
}
void mergesort(vector<int>& arr,int left,int right)
{if(left<right){int mid=left+(right-left)/2;mergesort(arr,left,mid);mergesort(arr,mid+1,right);merge(arr,left,mid,right);}
}

8.计数排序

void countingsort(vector<int>& arr)
{if(arr.empty()) return;int min=*min_element(arr.begin(),arr.end());int max=*max_element(arr.begin(),arr.end());int l=max-min+1;vector<int> result(l,0);for(int num:arr){result[num-min]++;      每个数出现了几次，哈希的思想}int index=0;for(int i=0;i<l;i++){int num=i+min;while(result[i]>0){arr[index]=num;result[i]--;index++;}}
}

9.总结