排序算法

原创

子建

修改于 2020-10-09 15:55:17

3290

修改于 2020-10-09 15:55:17

文章被收录于专栏：PTA-数据结构与算法PTA-数据结构与算法

Sort

需要注意的是，sort对一般数组排序 sort(A,A+100);即可

但是对于vector需要使用 a.begin() 来获取其指针。

sort(money.begin()+1,money.end(),cmp);

选择排序

找出最小的和首位交换...

void selectSort(int a[],int N){
	for(int i=0;i<N-1;i++){
		min=i;
		for(int j=i+1;j<N;j++)
			if(A[j]<A[min])
				min=j;
		swap(a[i], a[min]);
		
	}
}

插入排序

插入排序。注意，若后面一个元素比其前面一个元素小，则将这两个元素交换位置，指向左移一位然后再来比较这个元素与前面一个元素的大小，若小，则还需要交换这两个元素位置，一直到这个插入元素在正确的位置为止

void insertSort(int a[],  int length)
{
	for (int i = 1; i < length; i++){
		for (int j = i - 1; j >= 0 && a[j + 1] < a[j]; j--)
			swap(a[j], a[j + 1]);
	}
}

冒泡排序

void BubbleSort(int a[],int N){
    bool flag;
    for(int i=N-1;i>=0;i--){
    flag=false;
		for(int j=0;j<i;j++){
		if(a[j]>a[j+1]){
			swap(a[j],a[j+1]);
			flag=true;
		}
    }
    if(flag==false) break;
}

归并排序

void MergeSort (int arr [], int low,int high) {
    if(low>=high) { return; } // 终止递归的条件，子序列长度为1
    int mid =  low + (high - low)/2;  // 取得序列中间的元素
    MergeSort(arr,low,mid);  // 对左半边递归
    MergeSort(arr,mid+1,high);  // 对右半边递归
    merge(arr,low,mid,high);  // 合并
  }

void Merge(int arr[],int low,int mid,int high){
    //low为第1有序区的第1个元素，i指向第1个元素, mid为第1有序区的最后1个元素
    int i=low,j=mid+1,k=0;  //mid+1为第2有序区第1个元素，j指向第1个元素
    int *temp=new int[high-low+1]; //temp数组暂存合并的有序序列
    while(i<=mid&&j<=high){
        if(arr[i]<=arr[j]) //较小的先存入temp中
            temp[k++]=arr[i++];
        else
            temp[k++]=arr[j++];
    }
    while(i<=mid)//若比较完之后，第一个有序区仍有剩余，则直接复制到t数组中
        temp[k++]=arr[i++];
    while(j<=high)//同上
        temp[k++]=arr[j++];
    for(i=low,k=0;i<=high;i++,k++)//将排好序的存回arr中low到high这区间
	arr[i]=temp[k];
    delete []temp;//释放内存，由于指向的是数组，必须用delete []
}

void sort(int a []){
    int N = a.size();
    for (int size = 1; size < N; size *= 2){
      //  low+size=mid+1,为第二个分区第一个元素，它 < N，确保最后一次合并有2个区间
      for(int low = 0; low + size < N;low += 2 * size) {
        mid = low + size - 1;
        high = low + 2 * size - 1;
        if(high > N-1) high = N - 1;
        merge(a,low, mid, high);
      }
    }
  }

+++